結果
問題 | No.50 おもちゃ箱 |
ユーザー |
|
提出日時 | 2016-09-26 12:23:22 |
言語 | D (dmd 2.106.1) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,822 bytes |
コンパイル時間 | 1,215 ms |
コンパイル使用メモリ | 133,436 KB |
最終ジャッジ日時 | 2024-11-14 19:51:58 |
合計ジャッジ時間 | 1,688 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
Main.d(37): Error: no property `boxes` for `u` of type `std.typecons.Nullable!(used)` /home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/typecons.d(3238): struct `Nullable` defined here Main.d(37): Error: no property `volume` for `u` of type `std.typecons.Nullable!(used)` /home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/typecons.d(3238): struct `Nullable` defined here Main.d(38): Error: no property `boxes` for `u` of type `std.typecons.Nullable!(used)` /home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/typecons.d(3238): struct `Nullable` defined here Main.d(38): Error: no property `boxes` for `u` of type `std.typecons.Nullable!(used)` /home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/typecons.d(3238): struct `Nullable` defined here Main.d(39): Error: no property `boxes` for `u` of type `std.typecons.Nullable!(used)` /home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/typecons.d(3238): struct `Nullable` defined here Main.d(40): Error: no property `volume` for `u` of type `std.typecons.Nullable!(used)` /home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/typecons.d(3238): struct `Nullable` defined here Main.d(42): Error: no property `volume` for `u` of type `std.typecons.Nullable!(used)` /home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/typecons.d(3238): struct `Nullable` defined here /home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/algorithm/comparison.d(1768): Error: static assert: "Invalid arguments: Cannot compare types Nullable!(used) and Nullable!(used) for ordering." Main.d(47): instantiated from here: `min!(Nullable!(used), Nullable!(used))`
ソースコード
import std.algorithm, std.array, std.container, std.range, std.bitmanip; import std.numeric, std.math, std.bigint, std.random, core.bitop; import std.string, std.regex, std.conv, std.stdio, std.typecons; struct used { size_t boxes; int volume; int opCmp(used rhs) { if (boxes < rhs.boxes) return -1; else if (boxes > rhs.boxes) return 1; else if (volume < rhs.volume) return -1; else if (volume > rhs.volume) return 1; else return 0; } } void main() { auto n = readln.chomp.to!size_t; auto ai = readln.split.map!(to!int).array; auto m = readln.chomp.to!size_t; auto bi = readln.split.map!(to!int).array; bi.sort!("a > b"); auto memo = new Nullable!used[](1 << n); memo[0] = used(0, 0); foreach (i; 1..1 << n) { Nullable!used minU; foreach (j; 0..n) { if (i.bitTest(j)) { auto a = ai[j]; auto k = i.bitComp(j); auto u = memo[k]; if (u.isNull) continue; if (bi[u.boxes] - u.volume < a) { if (u.boxes == m - 1 || bi[u.boxes + 1] < a) continue; u.boxes += 1; u.volume = a; } else { u.volume += a; } if (minU.isNull) minU = u; else minU = min(minU, u); } } memo[i] = minU; } auto u = memo[$ - 1]; if (u.isNull) writeln(-1); else writeln(u.boxes + 1); } template BitOp(T) { bool bitTest(T n, size_t i) { return (n & (1.to!T << i)) != 0; } T bitSet(T n, size_t i) { return n | (1.to!T << i); } T bitReset(T n, size_t i) { return n & ~(1.to!T << i); } T bitComp(T n, size_t i) { return n ^ (1.to!T << i); } int bsf(T n) { return core.bitop.bsf(n.to!ulong); } int bsr(T n) { return core.bitop.bsr(n.to!ulong); } int popcnt(T n) { return core.bitop.popcnt(n.to!ulong); } } mixin BitOp!int;