結果

問題 No.50 おもちゃ箱
ユーザー te-shte-sh
提出日時 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言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
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))`

ソースコード

diff # 

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;
0