fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define pb push_back
  5. #define pii pair<int, int>
  6. #define fi first
  7. #define se second
  8. #define bit(i, x) ((x >> i) & 1)
  9. #define SZ(x) ((int)(x.size()))
  10. #define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
  11. #define FORD(i, a, b) for (int i = (a); i >= (b); --i)
  12. #define task "test"
  13. #define int long long
  14.  
  15. using namespace std;
  16.  
  17.  
  18. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  19. ll rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll>(l, r)(rd); }
  20.  
  21. const int MAXn = 5e5 + 5;
  22. const ll MOD = 1e9 + 7;
  23. const ll oo = LLONG_MAX;
  24. const int BASE = 3137;
  25. const int BL = 320;
  26.  
  27. int n,k,a[MAXn],dp[MAXn],res;
  28.  
  29. struct SegmentTree{
  30.     int N,it[MAXn*4];
  31.     void init(int n){
  32.         N=n;
  33.         for(int i=0;i<=N*4;i++){
  34.             it[i]=0;
  35.         }
  36.     }
  37.     void upd(int idx,int l,int r,int u,int v){
  38.         if (l>u||r<u)return;
  39.         if (l==r){
  40.             it[idx]=v;
  41.             return;
  42.         }
  43.         int mid=(l+r)>>1;
  44.         upd(idx<<1,l,mid,u,v);
  45.         upd(idx<<1|1,mid+1,r,u,v);
  46.         it[idx]=max(it[idx<<1],it[idx<<1|1]);
  47.     }
  48.     int get(int idx,int l,int r, int u, int v){
  49.         if (l>v||r<u)return -oo;
  50.         if (l>=u&&r<=v)return it[idx];
  51.         int mid =(l+r)>>1;
  52.         return max(get(idx<<1,l,mid,u,v),get(idx<<1|1,mid+1,r,u,v));
  53.     }
  54.     void update(int u,int v){upd(1,0,N,u,v);}
  55.     int query(int u,int v){return get(1,0,N,u,v);}
  56. }st;
  57.  
  58. void solution() {
  59.     cin>>n>>k;
  60.     for(int i=1;i<=n;i++){cin>>a[i],a[i]+=a[i-1];}
  61.     st.init(n);
  62.     for (int i=0;i<k&&i<=n;i++){
  63.         dp[i]=a[i]-a[i+1];
  64.         res=max(res,dp[i]);
  65.         st.update(i,dp[i]);
  66.     }
  67.     for (int i=k;i<=n;i++){
  68.         dp[i]=st.query(i-k,i-2)+a[i];
  69.         res=max(res,dp[i]);
  70.         st.update(i,dp[i]-a[i+1]);
  71.     }
  72.     cout<<res;
  73. }
  74.  
  75. //dp[i]=dp[j] + sum(j+2->i) (j<i-1)
  76.  
  77. int32_t main() {
  78.     if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
  79.     ios::sync_with_stdio(0); cin.tie(0);
  80.     int ntest = 1; //cin >> ntest;
  81.     while (ntest--) solution();
  82.     cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
  83. }
  84.  
Success #stdin #stdout #stderr 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
0.007035s
https://ideone.com/6W10Ps
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!