結果

問題 No.3424 Shooting Game
コンテスト
ユーザー pengin_2000
提出日時 2026-01-11 16:23:05
言語 C
(gcc 15.2.0)
結果
AC  
実行時間 154 ms / 2,000 ms
コード長 1,254 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 213 ms
コンパイル使用メモリ 39,816 KB
実行使用メモリ 14,280 KB
最終ジャッジ日時 2026-01-11 17:24:42
合計ジャッジ時間 1,843 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<stdio.h>
long long int max(long long int a, long long int b)
{
	if (a > b)
		return a;
	else
		return b;
}
long long int lazy[800005], ss;
void update(long long int a, long long int b, long long int v, long long int k, long long int l, long long int r)
{
	if (a <= l && r <= b)
		lazy[k] = max(lazy[k], v);
	else if (l < b && a < r)
	{
		update(a, b, v, 2 * k + 1, l, (l + r) / 2);
		update(a, b, v, 2 * k + 2, (l + r) / 2, r);
	}
	return;
}
long long int l[200005], r[200005], p[200005];
long long int dp[200005];
int main()
{
	long long int n, t;
	scanf("%lld %lld", &n, &t);
	long long int i;
	for (i = 0; i < n; i++)
		scanf("%lld %lld %lld", &l[i], &r[i], &p[i]);
	for (ss = 1; ss < 200005; ss *= 2);
	for (i = 0; i < 2 * ss - 1; i++)
		lazy[i] = 0;
	for (i = 0; i < n; i++)
		update(l[i], r[i] + 1, p[i], 0, 0, ss);
	for (i = 0; i < ss - 1; i++)
	{
		lazy[2 * i + 1] = max(lazy[2 * i + 1], lazy[i]);
		lazy[2 * i + 2] = max(lazy[2 * i + 2], lazy[i]);
	}
	dp[0] = lazy[ss - 1];
	for (i = 1; i < 200005; i++)
	{
		dp[i] = max(dp[i - 1], lazy[i + ss - 1]);
		if (i >= t)
			dp[i] = max(dp[i], dp[i - t] + lazy[i + ss - 1]);
	}
	long long int ans = 0;
	for (i = 0; i < 200005; i++)
		ans = max(ans, dp[i]);
	printf("%lld\n", ans);
	return 0;
}
0