結果

問題 No.844 split game
コンテスト
ユーザー 👑 希丝缇娜菲贝尔
提出日時 2026-09-01 21:32:05
言語 cLay
(20250308-1 + boost 1.92.0)
コンパイル:
clayc _filename_
実行:
./a.out
結果
AC  
実行時間 17 ms / 2,000 ms
+ 901µs
コード長 442 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,420 ms
コンパイル使用メモリ 198,944 KB
実行使用メモリ 9,984 KB
最終ジャッジ日時 2026-09-01 21:32:13
合計ジャッジ時間 7,139 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 56
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

using P = pair<int, ll>;
using VP = vector<P>;

int @n, @m; ll @a;
vector<VP> e(n + 1);
rep(m) {
	int @l, @r; ll @x;
	e[r].push_back({l, x}); 
} 

VLL f(n + 1, -ll_inf); // f_{i, j} := 到第 i 个位置，最后一刀在 (j, j + 1) 之间的最大贡献
f[0] = 0;
ll mx = 0;
rep(i, 1, n + 1) {
	f[i] = mx - a;
	for(auto x : e[i]) {
		f[i] >?= f[x.first - 1] + x.second - (i == n ? 0 : a);
	}
	mx >?= f[i];
}
for(auto x : f) mx >?= x;
wt(mx);
0