Josif_tepe

Untitled

May 3rd, 2026
269
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <deque>
  4. using namespace std;
  5. typedef long long ll;
  6. const int maxn = 1e6 + 5;
  7. const ll INF = 1e18;
  8. ll v[maxn];
  9.  
  10. ll B(int i) {
  11.     return v[i] + i;
  12. }
  13. int main(){
  14.     ios_base::sync_with_stdio(false);
  15.     int n;
  16.     ll k;
  17.     cin >> n >> k;
  18.    
  19.     vector<ll> pref(n + 1, 0);
  20.     for(int i = 0; i < n; i++) {
  21.         cin >> v[i];
  22.     }
  23.    
  24.     for(int i = 0; i < n; i++) {
  25.         pref[i + 1] = pref[i] + v[i];
  26.     }
  27.    
  28.     deque<int> dq;
  29.     ll res = INF;
  30.    
  31.     for(int i = 0; i < n; i++) {
  32.         while(!dq.empty() and B(dq.back()) >= B(i)) {
  33.             dq.pop_back();
  34.         }
  35.         dq.push_back(i);
  36.         int p = i - k + 1;
  37.         if(p < 0) {
  38.             continue;
  39.         }
  40.        
  41.         while(!dq.empty() and dq.front() < p) {
  42.             dq.pop_front();
  43.         }
  44.        
  45.         ll x_max = B(dq.front()) - p;
  46.         if(x_max < k) {
  47.             continue;
  48.         }
  49.        
  50.         ll sum = pref[p + k] - pref[p];
  51.         ll to_cut = sum - (k * x_max) + (k * (k - 1) / 2);
  52.         ll t = 10LL * p + 5LL * to_cut;
  53.        
  54.         res = min(res, t);
  55.        
  56.     }
  57.    
  58.     if(res == INF){
  59.         res = -1;
  60.     }
  61.     cout << res << endl;
  62.     return 0;
  63. }
  64.  
  65.  
  66.  
Advertisement
Add Comment
Please, Sign In to add comment