Advertisement
Guest User

Untitled

a guest
Jul 22nd, 2019
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.86 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define st first
  4. #define nd second
  5. using namespace std;
  6. const int N = 3e5+1;
  7. int n;
  8. ll m, k, ans;
  9. int main() {
  10.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  11.     cin>>n>>m>>k;
  12.     vector<int> a(n);
  13.     vector<ll> pref(n);
  14.     for(int i=0; i<n; ++i) {
  15.         cin>>a[i];
  16.         pref[i]=a[i];
  17.         if(i!=0) pref[i]+=pref[i-1];
  18.     }
  19.     for(int mod=0; mod<m; ++mod) {
  20.         vector<pair<ll, int>> b(n);
  21.         for(int i=mod; i<n; ++i) {
  22.             b[i].st=pref[i];
  23.             if(mod!=0) b[i].st-=pref[mod-1];
  24.             b[i].st-=k*((ll)(i-mod)/m+(ll)1);
  25.             b[i].nd=i;
  26.         }
  27.         sort(b.begin(), b.end());
  28.         reverse(b.begin(), b.end());
  29.         int j = 0;
  30.         for(int i=0; mod+i*m<n; i++) {
  31.             while(j<n-1 && b[j].nd<mod+i*m) {
  32.                 j++;
  33.             }
  34.             ans = max(ans, b[j].st+(ll)i*k-( ((mod+i*m==0)? 0 : pref[mod+i*m-1]) - ((mod==0)? 0 : pref[mod-1]) ));
  35.         }
  36.     }
  37.     cout<<ans;
  38. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement