nickel2halide

F7

Oct 20th, 2012
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.62 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. const int MAXN = 300005;
  7.  
  8. int N;
  9. int B[MAXN];
  10.  
  11. int rmax[MAXN];
  12.  
  13. int main() {
  14.     cin >> N;
  15.     for (int i = 0; i < N; ++i) {
  16.         cin >> B[i];
  17.     }
  18.  
  19.     sort(B, B+N);
  20.     rmax[0] = 0;
  21.     for (int i = 0; i < N; ++i) {
  22.         rmax[i + 1] = max(rmax[i], B[i] + N - i + 1);
  23.     }
  24.  
  25.     int ct = 0;
  26.     int right = 0;
  27.     for (int i = N - 1; i >= 0; --i) {
  28.         if (B[i] + N >= rmax[i] && B[i] + N >= right) {
  29.             ++ct;
  30.         }
  31.         right = max(right, B[i] + N - i);
  32.     }
  33.  
  34.     cout << ct << '\n';
  35.  
  36.     return 0;
  37. }
Advertisement
Add Comment
Please, Sign In to add comment