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

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

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

コンパイルメッセージ

In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/16.2.0/include/c++/16/algorithm:63,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/16.2.0/include/c++/16/x86_64-pc-linux-gnu/bits/stdc++.h:51,
                 from main.cpp:1:
In function 'constexpr _ForwardIterator std::__max_element(_ForwardIterator, _ForwardIterator, _Compare) [with _ForwardIterator = const long long int*; _Compare = less<void>]',
    inlined from 'constexpr _ForwardIterator std::__max_element(_ForwardIterator, _ForwardIterator, _Compare) [with _ForwardIterator = const long long int*; _Compare = less<void>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/16.2.0/include/c++/16/bits/stl_algo.h:5662:5,
    inlined from 'constexpr _Tp std::max(initializer_list<_Tp>) [with _Tp = long long int]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/16.2.0/include/c++/16/bits/stl_algo.h:5749:44,
    inlined from 'void main_()' at main.cpp:102:25:
/home/linuxbrew/.linuxbrew/Cellar/gcc/16.2.0/include/c++/16/bits/stl_algo.h:5668:9: warning: 'two_tmp' may be used uninitialized [-Wmaybe-uninitialized]
 5668 |         if (__comp(*__result, *__first))
      |         ^~
main.cpp: In function 'void main_()':
main.cpp:91:47: note: 'two_tmp' was declared here
   91 |                         ll zero_tmp, one_tmp, two_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);
			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, 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;
}