#include using namespace std; #define ll long long #define rep(i, n) for (int i = 0; i < (int)(n); i++) template bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;} template bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;} const long long mod=998244353; const long long mod2=469762049; const long long mod100=1000000007; template struct lazysegtree{ using F1=function; using F2=function; using F3=function; vectornode; vectorlazy; int N;int log;F1 op;T e;F2 mapping;F3 composition;F id; lazysegtree(int n,F1 op,T e,F2 mapping,F3 composition,F id) :op(op),e(e),mapping(mapping),composition(composition),id(id){ N=1; log=1; while(N=0;i--){ lazy[pos*2]=composition(lazy[pos*2],lazy[pos]); lazy[pos*2+1]=composition(lazy[pos*2+1],lazy[pos]); node[pos*2]=mapping(node[pos*2],lazy[pos]); node[pos*2+1]=mapping(node[pos*2+1],lazy[pos]); lazy[pos]=id; pos<<=1; if((p>>i)&1) pos++; } lazy[pos]=id; node[pos]=x; while(pos>=2){ pos/=2; node[pos]=op(node[pos*2],node[pos*2+1]); } return; } void apply(int l,int r,int a,int b,int u,F f){ if(b<=l || r<=a) return; if(l<=a && b<=r){ lazy[u]=composition(lazy[u],f); node[u]=mapping(node[u],f); return; } lazy[u*2]=composition(lazy[u*2],lazy[u]); lazy[u*2+1]=composition(lazy[u*2+1],lazy[u]); node[u*2]=mapping(node[u*2],lazy[u]); node[u*2+1]=mapping(node[u*2+1],lazy[u]); lazy[u]=id; int m=(a+b)/2; apply(l,r,a,m,u*2,f); apply(l,r,m,b,u*2+1,f); node[u]=op(node[u*2],node[u*2+1]); return; } void apply(int l,int r,F f){//[l,r)を変更 l++;r++; apply(l,r,1,N+1,1,f); } void apply(int p,F f){ apply(p,p+1,f); } T fold(int l,int r,int a,int b,int u){ if(b<=l || r<=a)return e; if(l<=a && b<=r){ return node[u]; } int m=(a+b)/2; T L=mapping(fold(l,r,a,m,u*2),lazy[u]); T R=mapping(fold(l,r,m,b,u*2+1),lazy[u]); return op(L,R); } T fold(int l,int r){//[l,r)をを求める l++;r++; return fold(l,r,1,N+1,1); } T fold(int p){ p++; return fold(p,p+1,1,N+1,1); } }; int main(){ cout.tie()->sync_with_stdio(0); cin.tie(0); int N,B,C;cin>>N>>B>>C; ll A[N+1]; for(int i=1;i<=N;i++) cin>>A[i]; auto op=[](ll a,ll b){return max(a,b);}; auto mapping=[](ll a,ll b){return a+b;}; lazysegtreeseg(N+2,op,0LL,mapping,mapping,0LL); for(int i=1;i<=N+1;i++){ int l=i-C; if(l<0) l=0; ll now=seg.fold(l,i); if(B==2) now=seg.fold(l,i-1); seg.set(i,now); if(i<=N) seg.apply(0,i,A[i]); } cout<