結果

問題 No.50 おもちゃ箱
コンテスト
ユーザー ゴリポン先生
提出日時 2025-08-09 14:07:52
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 10 ms / 5,000 ms
コード長 748 bytes
コンパイル時間 3,053 ms
コンパイル使用メモリ 170,592 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-09 14:07:57
合計ジャッジ時間 4,797 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

module main;
// https://kmjp.hatenablog.jp/entry/2015/07/16/1000 より
// ビットDP
import std;

void main()
{
	// 入力
	auto N = readln.chomp.to!int;
	auto A = readln.split.to!(int[]);
	auto M = readln.chomp.to!int;
	auto B = readln.split.to!(int[]);
	// 答えの計算と出力
	auto MA = new int[](1 << 11);
	foreach (i; 0 .. 1 << N)
		foreach (j; 0 .. N)
			if (i & (1 << j))
				MA[i] += A[j];
	B.sort!"a > b";
	auto dp = new bool[][](12, 1 << 10);
	dp[0][0] = true;
	foreach (i; 0 .. M) {
		foreach (mask; 0 .. 1 << N)
			foreach (mask2; 0 .. 1 << N)
				if (!(mask & mask2) && dp[i][mask] && MA[mask2] <= B[i])
					dp[i + 1][mask | mask2] = true;

		if (dp[i + 1][(1 << N) - 1]) {
			writeln(i + 1);
			return;
		}
	}
	writeln(-1);
}
0