結果

問題 No.107 モンスター
ユーザー ゴリポン先生
提出日時 2025-08-28 09:31:32
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 778 bytes
コンパイル時間 4,231 ms
コンパイル使用メモリ 165,592 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-28 09:31:38
合計ジャッジ時間 5,557 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

module main;
// http://rsujskf.s602.xrea.com/?yukicoder_107 より
// ビットDP
import std;

void main()
{
	// 入力
	int N = readln.chomp.to!int;
	auto D = readln.split.to!(int[]);
	// 答えの計算
	auto mx = new int[](1 << N);	// モンスターを倒していったときの最大HP
	mx[0] = 100;
	foreach (i; 1 .. 1 << N) {
		foreach (j; 0 .. N) if (i & (1 << j)) {
			if (D[j] < 0) mx[i] = mx[i - (1 << j)] + 100;
			else mx[i] = mx[i - (1 << j)];
			break;
		}
	}
	auto dp = new int[](1 << N);
	dp[0] = 100;
	foreach (i; 0 .. 1 << N) {
		if (dp[i] == 0) continue;
		foreach (j; 0 .. N) if ((i & (1 << j)) == 0) {
			int k = min(dp[i] + D[j], mx[i + (1 << j)]);
			dp[i + (1 << j)] = max(dp[i + (1 << j)], k);
		}
	}
	// 答えの出力
	writeln(dp[(1 << N) - 1]);
}
0