Advertisement
PikMike

Untitled

Oct 16th, 2016
391
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.11 KB | None | 0 0
  1. #include<iostream>
  2. #include<string>
  3. #include<math.h>
  4. #include<algorithm>
  5. #include<vector>
  6. #include<map>
  7. #include<time.h>
  8. #include<set>
  9. #include<stdio.h>
  10. using namespace std;
  11. const long long ma = 10000000;
  12. long long i, n, k, w, v, a[110001] = { 0 }, b[110001] = { 0 }, c[110001] = { 0 }, kr, x, kra[110001] = { 0 };
  13. int main() {
  14.  
  15.     cin >> n >> k >> w >> v;
  16.     for (i = 0; i < n; i++) {
  17.         kra[i] = -1;
  18.         cin >> a[i];
  19.             if (a[i] >= w)
  20.                 b[i] = 1;
  21.        
  22.         if (v != 0 && b[i] != 0)
  23.             b[i] = min(k,max(b[i], (a[i] - w) / v));
  24.         else if (b[i] != 0)
  25.             b[i] = min(k,i);
  26.         b[i] = min(b[i], max(k, long long(1)));
  27.         if (a[i] >= w)
  28.             b[i] = max(b[i],long long(1));
  29.     }
  30.  
  31.     kra[0] = n - 1 - b[n - 1];
  32.     kr = kra[0];
  33.     x = 0;
  34.     for (i = n - 2; i >= 0; i--) {
  35.         if (c[i] == 0)
  36.         {
  37.             if (kr <= i)
  38.                 c[i] = x + 1;
  39.             else {
  40.                 while (kra[x] > i && x < n && kra[x] != -1) {
  41.                     x++;
  42.                 }
  43.                 kr = kra[x];
  44.                 if (x == n) {
  45.                     cout << -1;
  46.                     return 0;
  47.                 }
  48.                 c[i] = x + 1;
  49.             }
  50.             if (kra[c[i]] == -1 || kra[c[i]]>i - b[i])
  51.                 kra[c[i]] = i - b[i];
  52.         }
  53.     }
  54.     cout << c[0] << "\n";
  55.     return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement