#include #include #ifndef IO_HPP #define IO_HPP #include #include #include #include #include #include #include #include #include using namespace std; templateistream &operator>>(istream&,pair&); templateistream &operator>>(istream&,tuple&a); templateistream &operator>>(istream&is,vector&a); templateistream &operator>>(istream&is,array&a); template istream &operator>>(istream&is,pair&a){ is>>a.first>>a.second; return is; } template void read_tuple(istream&is,tuple&a){ if constexpr(pos>::value){ is>>get(a); read_tuple(is,a); } } template istream &operator>>(istream&is,tuple&a){ read_tuple<0>(is,a); return is; } template istream &operator>>(istream&is,vector&a){ for(T&x:a)is>>x; return is; } template istream &operator>>(istream&is,array&a){ for(T&x:a)is>>x; return is; } templateostream &operator<<(ostream&os,const pair&); templateostream &operator<<(ostream&os,const tuple&); templateostream &operator<<(ostream&os,const vector&); templateostream &operator<<(ostream&os,priority_queue); templateostream &operator<<(ostream&os,queue); templateostream &operator<<(ostream&os,deque); templateostream &operator<<(ostream&os,stack); templateostream &operator<<(ostream&os,const array&); templateostream &operator<<(ostream&os,const map&); templateostream &operator<<(ostream&os,const unordered_map&); templateostream &operator<<(ostream&os,const set&); templateostream &operator<<(ostream&os,const multiset&); templateostream &operator<<(ostream&os,const unordered_set&); template ostream &operator<<(ostream&os,const pair&a){ os< void write_tuple(ostream&os,const tuple&a){ if constexpr(pos>::value){ if constexpr(pos>0)os<<' '; os<(a); write_tuple(os,a); } } template ostream &operator<<(ostream&os,const tuple&a){ write_tuple<0>(os,a); return os; } template ostream &operator<<(ostream&os,const vector&a){ os<<'{'; for(int i=0;i<(int)a.size();i++){ os< ostream &operator<<(ostream&os,priority_queuea){ os<<'{'; if(!a.empty()){ os< ostream &operator<<(ostream&os,queuea){ os<<'{'; if(!a.empty()){ os< ostream &operator<<(ostream&os,dequea){ os<<'{'; if(!a.empty()){ os< ostream &operator<<(ostream&os,stacka){ os<<'{'; if(!a.empty()){ os< ostream &operator<<(ostream&os,const array&a){ os<<'{'; for(int i=0;i<(int)a.size();i++){ os< ostream &operator<<(ostream&os,const map&a){ if(a.empty()){ os<<"{}"; return os; } auto itr=a.begin(); os<<"{["<first<<","<second<<']'; while(++itr!=a.end())os<<",["<first<<','<second<<']'; os<<'}'; return os; } template ostream &operator<<(ostream&os,const unordered_map&a){ if(a.empty()){ os<<"{}"; return os; } auto itr=a.begin(); os<<"{["<first<<","<second<<']'; while(++itr!=a.end())os<<",["<first<<','<second<<']'; os<<'}'; return os; } template ostream &operator<<(ostream&os,const set&a){ if(a.empty()){ os<<"{}"; return os; } auto itr=a.begin(); os<<'{'<<*itr; while(++itr!=a.end())os<<','<<*itr; os<<'}'; return os; } template ostream &operator<<(ostream&os,const multiset&a){ if(a.empty()){ os<<"{}"; return os; } auto itr=a.begin(); os<<'{'<<*itr; while(++itr!=a.end())os<<','<<*itr; os<<'}'; return os; } template ostream &operator<<(ostream&os,const unordered_set&a){ if(a.empty()){ os<<"{}"; return os; } auto itr=a.begin(); os<<'{'<<*itr; while(++itr!=a.end())os<<','<<*itr; os<<'}'; return os; } #endif using namespace std; using ll=long long; using ull=unsigned long long; using P=pair; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templatevoid operator++(pair&a,int){a.first++,a.second++;} templatevoid operator--(pair&a,int){a.first--,a.second--;} templatevoid operator++(vector&a,int){for(auto &i:a)i++;} templatevoid operator--(vector&a,int){for(auto &i:a)i--;} using vref=typename vector::reference; vref operator|=(vref a,bool b){a=a|b;return a;} vref operator&=(vref a,bool b){a=a&b;return a;} vref operator^=(vref a,bool b){a=a^b;return a;} #define overload3(_1,_2,_3,name,...) name #define rep1(i,n) for(int i=0;i<(int)(n);i++) #define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++) #define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__) #define reps(i,l,r) rep2(i,l,r) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) #define fin(x) return cout<<(x)<<'\n',static_cast(0) #define yn(x) cout<<((x)?"Yes\n":"No\n") #define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end()) template inline int fkey(vector&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();} ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } #ifdef LOCAL #include #define SWITCH(a,b) (a) #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) #define SWITCH(a,b) (b) #endif struct Timer{ clock_t start; Timer(){ start=clock(); ios::sync_with_stdio(false); cin.tie(nullptr); cout<>testcase; for(int i=0;i #include template constexpr std::enable_if_t::digits<=32,int>msb(T n){return n==0?-1:31-__builtin_clz(n);} template constexpr std::enable_if_t<(std::numeric_limits::digits>32),int>msb(T n){return n==0?-1:63-__builtin_clzll(n);} template constexpr std::enable_if_t::digits<=32,int>lsb(T n){return n==0?-1:__builtin_ctz(n);} template constexpr std::enable_if_t<(std::numeric_limits::digits>32),int>lsb(T n){return n==0?-1:__builtin_ctzll(n);} template constexpr std::enable_if_t,T>floor_pow2(T n){return n==0?0:T(1)< constexpr std::enable_if_t,T>ceil_pow2(T n){return n<=1?1:T(1)<<(msb(n-1)+1);} template constexpr T safe_div(T a,T b){return a/b-(a%b&&(a^b)<0);} template constexpr T safe_ceil(T a,T b){return a/b+(a%b&&(a^b)>0);} template struct SegmentTree{ using S=typename M::S; private: int n,z; std::vectordat; public: SegmentTree():n(0),z(0),dat(){} explicit SegmentTree(int n):n(n),z(ceil_pow2(n)),dat(ceil_pow2(n)*2,M::e()){} explicit SegmentTree(const std::vector&a):n(a.size()),z(ceil_pow2((int)a.size())){ dat.resize(z*2,M::e()); for(int i=0;i=1;i--)dat[i]=M::op(dat[i*2],dat[i*2+1]); } SegmentTree(int n,S init):SegmentTree(std::vector(n,init)){} inline S get(int i)const{return dat[i+z];} void set(int i,S x){ assert(0<=i&&i>=1; while(i){ dat[i]=M::op(dat[i*2],dat[i*2+1]); i>>=1; } } S prod(int l,int r)const{ assert(0<=l&&l<=r&&r<=n); if(r==n)r=z; l+=z,r+=z; S left=M::e(),right=M::e(); while(l>=1,r>>=1; } return M::op(left,right); } inline S all_prod()const{return dat[1];} template int max_right(int l,const Func&f)const{ if(l==n)return n; l+=z; S now=M::e(); do{ while((~l)&1)l>>=1; S nxt=M::op(now,dat[l]); if(f(nxt))now=nxt,l++; else{ while(l int min_left(int r,const Func&f)const{ if(r==0)return 0; r+=z; S now=M::e(); do{ r--; while(r>1&&(r&1))r>>=1; S nxt=M::op(dat[r],now); if(f(nxt))now=nxt; else{ while(r::min()> struct MonoidMax{ using S=T; static inline S op(const S&x,const S&y){return x static inline S pow(const S&x,U){return x;} }; void SOLVE(){ int n,b,c; cin>>n>>b>>c; vectora(n); cin>>a; a.push_back(0); for(int i=n-1;i>=0;i--)a[i]+=a[i+1]; SegmentTree>dp(n+1),ep(n+1); dp.set(0,a[0]); ep.set(0,0); rep(i,1,n+1){ dp.set(i,ep.prod(max(0,i-b+1),i)+a[i]); ep.set(i,dp.prod(max(0,i-c+1),i)-a[i]); } cout<