Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define ll long long
- #define st first
- #define nd second
- using namespace std;
- const int N = 3e5+1;
- int n;
- ll m, k, ans;
- int main() {
- ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- cin>>n>>m>>k;
- vector<int> a(n);
- vector<ll> pref(n);
- for(int i=0; i<n; ++i) {
- cin>>a[i];
- pref[i]=a[i];
- if(i!=0) pref[i]+=pref[i-1];
- }
- for(int mod=0; mod<m; ++mod) {
- vector<pair<ll, int>> b(n);
- for(int i=mod; i<n; ++i) {
- b[i].st=pref[i];
- if(mod!=0) b[i].st-=pref[mod-1];
- b[i].st-=k*((ll)(i-mod)/m+(ll)1);
- b[i].nd=i;
- }
- sort(b.begin(), b.end());
- reverse(b.begin(), b.end());
- int j = 0;
- for(int i=0; mod+i*m<n; i++) {
- while(j<n-1 && b[j].nd<mod+i*m) {
- j++;
- }
- 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]) ));
- }
- }
- cout<<ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement