結果

問題 No.54 Happy Hallowe'en
ユーザー ゴリポン先生
提出日時 2025-08-10 22:06:32
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 89 ms / 5,000 ms
コード長 663 bytes
コンパイル時間 4,707 ms
コンパイル使用メモリ 204,728 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-10 22:06:39
合計ジャッジ時間 6,600 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #

module main;
// https://kmjp.hatenablog.jp/entry/2015/07/19/1000 より
// 動的計画法
import std;

void main()
{
	// 入力
	auto N = readln.chomp.to!int;
	auto V = new int[](N), T = new int[](N);
	foreach (i; 0 .. N)
		readln.chomp.formattedRead("%d %d", V[i], T[i]);
	// 答えの計算と出力
	alias P = Tuple!(int, int);
	auto pair = new P[](N);
	foreach (i; 0 .. N)
		pair[i] = P(V[i] + T[i], i);
	pair.sort;

	auto ok = new bool[](20_001);
	ok[0] = true;
	foreach (i; 0 .. N)
		foreach_reverse (x; 0 .. T[pair[i][1]])
			if (ok[x])
				ok[x + V[pair[i][1]]] = 1;

	foreach_reverse (i; 0 .. 20_001) {
		if (ok[i]) {
			writeln(i);
			return;
		}
	}
}
0