#1191351 (C++23(gcc16)) No.3760 Streaming Schedule

• 問題: No.3760 Streaming Schedule
• ユーザー: kyoprouno
• 提出日時: 2026-10-03 18:03:01
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 529 ms / 2,000 ms
• コード長: 2,534 bytes
• コンパイル時間: 2,434 ms
• コンパイル使用メモリ: 371,360 KB
• 実行使用メモリ: 45,576 KB
• 最終ジャッジ日時: 2026-10-09 20:51:43
• 合計ジャッジ時間: 8,959 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge5_0

ファイルパターン	結果
sample	AC * 3
other	AC * 47

コンパイルメッセージ

main.cpp: In function 'void main_()':
main.cpp:98:32: warning: 'two_tmp' may be used uninitialized [-Wmaybe-uninitialized]
   98 |                         two.add(i+1,i+2,two_tmp);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~
main.cpp:90:47: note: 'two_tmp' was declared here
   90 |                         ll zero_tmp, one_tmp, two_tmp;
      |                                               ^~~~~~~
main.cpp:97:32: warning: 'one_tmp' may be used uninitialized [-Wmaybe-uninitialized]
   97 |                         one.add(i+1,i+2,one_tmp);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~
main.cpp:90:38: note: 'one_tmp' was declared here
   90 |                         ll zero_tmp, one_tmp, two_tmp;
      |                                      ^~~~~~~
main.cpp:80:32: warning: 'one_tmp' may be used uninitialized [-Wmaybe-uninitialized]
   80 |                         one.add(i+1,i+2,one_tmp);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~
main.cpp:74:38: note: 'one_tmp' was declared here
   74 |                         ll zero_tmp, one_tmp;
      |                                      ^~~~~~~

ソースコード

#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);
			

			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));
			
			if(i)two_tmp = one.getmax(i,i+1);

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

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

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

		}
	}
	
	

	cout << ans << endl;



	

	
};

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