#1192452 (C++23) No.3760 Streaming Schedule

• 問題: No.3760 Streaming Schedule
• ユーザー: ZeriToki
• 提出日時: 2026-10-09 22:46:07
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 3,283 bytes
• コンパイル時間: 2,117 ms
• コンパイル使用メモリ: 342,964 KB
• 実行使用メモリ: 22,236 KB
• 最終ジャッジ日時: 2026-10-09 22:46:40
• 合計ジャッジ時間: 7,811 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge4_1

ファイルパターン	結果
sample	AC * 3
other	AC * 45 WA * 2

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> 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<typename T,typename F> struct lazysegtree{
    using F1=function<T(T,T)>;
    using F2=function<T(T,F)>;
    using F3=function<F(F,F)>;
    vector<T>node;
    vector<F>lazy;
    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<n){
            N<<=1;
            log++;
        }
        node.assign(N*2,e);
        lazy.assign(N*2,id);
    }
    void set(int p,T x){
        int pos=1;
        for(int i=log-2;i>=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];
    //assert(B!=2);

    
    auto op=[](ll a,ll b){return max(a,b);};
    auto mapping=[](ll a,ll b){return a+b;};
    lazysegtree<ll,ll>seg(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);
        seg.set(i,now);
        if(i<=N) seg.apply(0,i,A[i]);
        
    }
    cout<<seg.fold(N+1,N+2)<<endl;
}