結果
問題 | No.50 おもちゃ箱 |
ユーザー |
![]() |
提出日時 | 2016-11-15 18:01:39 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 149 ms / 5,000 ms |
コード長 | 1,896 bytes |
コンパイル時間 | 1,532 ms |
コンパイル使用メモリ | 150,636 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-12 05:05:25 |
合計ジャッジ時間 | 3,574 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
コンパイルメッセージ
Main.d(30): Deprecation: foreach: loop index implicitly converted from `size_t` to `int` Main.d(35): Deprecation: foreach: loop index implicitly converted from `size_t` to `int` Main.d(41): Deprecation: foreach: loop index implicitly converted from `size_t` to `int`
ソースコード
import std.algorithm; import std.array; import std.ascii; import std.container; import std.conv; import std.math; import std.numeric; import std.range; import std.stdio; import std.string; import std.typecons; import core.bitop; void log(A...)(A arg) { stderr.writeln(arg); } int size(T)(in T s) { return cast(int)s.length; } void main() { int N; readf("%d\n", &N); auto A = readln.chomp.split(" ").map!(to!int).array; int M; readf("%d\n", &M); auto B = readln.chomp.split(" ").map!(to!int).array; auto pos = new int[][M]; for (int bit = 0; bit < (1<<N); bit++) { int sum = 0; foreach (int i, a; A) { if (bit & (1 << i)) { sum += a; } } foreach (int i, b; B) { if (b >= sum) { pos[i] ~= bit; } } } foreach (int i, b; B) { auto del = new bool[pos[i].size]; foreach (j, p; pos[i]) { foreach (k, q; pos[i]) { if (j == k) continue; if ((p & q) == q) { del[k] = true; } } } int[] npos; foreach (j, p; pos[i]) { if (del[j]) continue; npos ~= p; } pos[i] = npos; } auto dp = new bool[][](1<<N, 1<<M); dp[0][0] = true; for (int a = 0; a < (1<<N); a++) { for (int b = 0; b < (1<<M); b++) { if (! dp[a][b]) continue; for (int j = 0; j < M; j++) { if (b & (1 << j)) continue; foreach (p; pos[j]) { dp[a | p][b | (1<<j)] = true; } } } } int ans = 40; for (int b = 0; b < (1<<M); b++) { if (dp[(1<<N) - 1][b]) { ans = min(ans, popcnt(b)); } } if (ans == 40) ans = -1; writeln(ans); }