結果

問題 No.3760 Streaming Schedule
コンテスト
ユーザー kyoprouno
提出日時 2026-10-03 17:54:19
言語 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
結果
WA  
実行時間 -
コード長 2,213 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,320 ms
コンパイル使用メモリ 368,288 KB
実行使用メモリ 45,780 KB
最終ジャッジ日時 2026-10-09 20:51:47
合計ジャッジ時間 9,803 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge4_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17 WA * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'void main_()':
main.cpp:81:24: warning: 'two_tmp' may be used uninitialized [-Wmaybe-uninitialized]
   81 |                 two.add(i+1,i+2,two_tmp);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~
main.cpp:73:39: note: 'two_tmp' was declared here
   73 |                 ll zero_tmp, one_tmp, two_tmp;
      |                                       ^~~~~~~
main.cpp:80:24: warning: 'one_tmp' may be used uninitialized [-Wmaybe-uninitialized]
   80 |                 one.add(i+1,i+2,one_tmp);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~
main.cpp:73:30: note: 'one_tmp' was declared here
   73 |                 ll zero_tmp, one_tmp, two_tmp;
      |                              ^~~~~~~

ソースコード

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]);
	
	for(int i = 0; i < n; i++){
		ll zero_tmp, one_tmp, two_tmp;
		zero_tmp = max(one.getmax(max(0LL,(ll)i+1-c),i+1), two.getmax(max(0LL,(ll)i+1-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;
}
0