結果

問題 No.3760 Streaming Schedule
コンテスト
ユーザー kyoprouno
提出日時 2026-10-03 18:19:13
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 530 ms / 2,000 ms
+ 220µs
コード長 2,622 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,417 ms
コンパイル使用メモリ 369,440 KB
実行使用メモリ 45,680 KB
最終ジャッジ日時 2026-10-09 20:52:03
合計ジャッジ時間 8,582 ms
ジャッジサーバーID
（参考情報） 		judge5_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

template <class T, class U>
inline bool chmax(T &a, const U &b) { return a < b ? a = b, true : false; }

struct LazySegmentTree{
private:
    int n;
    vector<ll> node, lazy;
public:
    LazySegmentTree(vector<ll> v){
        int sz= v.size();
        n=1;
        while(n<sz) n*=2;
        node.resize(2*n-1);
        lazy.resize(2*n-1,0);
        for(int i=0; i<sz; i++) node[i+n-1]=v[i];
        for(int i=n-2; i>=0; i--) node[i]=max(node[2*i+1],node[2*i+2]);
    }
    void eval(ll k,ll l,ll r){
        if(lazy[k]!=0){
            node[k]+=lazy[k];
            if(r-l>1){
                lazy[2*k+1]+=lazy[k];
                lazy[2*k+2]+=lazy[k];
            }
            lazy[k]=0;
        }
    }
    void add(ll a,ll b,ll x,ll k=0,ll l=0,ll r=-1){
        if(r<0) r=n;
        eval(k,l,r);
        if(b<=l || r<=a) return;
        if(a<=l && r<=b){
            lazy[k]+=x;
            eval(k,l,r);
        }
        else{
            add(a,b,x,2*k+1,l,(l+r)/2);
            add(a,b,x,2*k+2,(l+r)/2,r);
            node[k]=max(node[2*k+1],node[2*k+2]);
        }
    }
    ll getmax(ll a,ll b,ll k=0,ll l=0,ll r=-1){
        if(r<0) r=n;
        if(b<=l || r<=a) return 0;
        eval(k,l,r);
        if(a<=l && r<=b) return node[k];
        ll vl=getmax(a,b,2*k+1,l,(l+r)/2);
        ll vr=getmax(a,b,2*k+2,(l+r)/2,r);
        return max(vl,vr);
    }
};


void main_() {
	int n,b,c;
	cin >> n >> b >> c;

	vector<ll> a(n);
	for(int i = 0; i < n; i++)cin >> a[i];

	vector<vector<ll>> dp(2,vector<ll>(n+1));

	ll ans = 0;

	LazySegmentTree one(dp[0]), two(dp[1]);

	if(b == 2){
		for(int i = 0; i < n; i++){
			ll zero_tmp, one_tmp;
			zero_tmp = one.getmax(max(0LL,(ll)i+2-c),i+1) + a[i];

			if(i)one_tmp = one.getmax(max(0LL,(ll)i+1-c),i);
			else one_tmp = 0;
			

			one.add(i+1,i+2,one_tmp);

			if(i == n-1)ans = max(zero_tmp, one_tmp);

			one.add(0,i+1,a[i]);
			

		}
	} else {
		for(int i = 0; i < n; i++){
			ll zero_tmp, one_tmp, two_tmp;
			zero_tmp = max(one.getmax(max(0LL,(ll)i+2-c),i+1), two.getmax(max(0LL,(ll)i+2-c),i+1)) + a[i];

			if(i)one_tmp = max(one.getmax(max(0LL,(ll)i+1-c),i), two.getmax(max(0LL,(ll)i+1-c),i));
			else one_tmp = 0;
			
			if(i)two_tmp = one.getmax(i,i+1);

			one.add(i+1,i+2,one_tmp);
			if(i)two.add(i+1,i+2,two_tmp);

			if(i == n-1){
				ans = max({zero_tmp, one_tmp});
				if(n > 1)chmax(ans, two_tmp);
			}

			one.add(0,i+1,a[i]);
			if(i)two.add(0,i+1,a[i]);
			

		}
	}
	
	

	cout << ans << endl;



	

	
};

 
int main() {
	int t = 1;
	// cin >> t;
	while(t--) main_();
	return 0;
}
0