結果

問題 No.50 おもちゃ箱
コンテスト
ユーザー te-sh
提出日時 2016-09-06 14:00:36
言語 D
(dmd 2.109.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,383 bytes
コンパイル時間 498 ms
コンパイル使用メモリ 130,276 KB
最終ジャッジ日時 2024-11-14 19:48:53
合計ジャッジ時間 958 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
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 `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(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(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 `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(41): 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(43): 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(48):        instantiated from here: `min!(Nullable!(used), Nullable!(used))`

ソースコード

diff #
raw source code 

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.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 (size_t i; 1..1 << n) {
    Nullable!used minU;
    foreach (size_t j; 0..n) {
      if (bt(&i, j)) {
        auto a = ai[j];
        auto k = i;
        btc(&k, j);
        auto u = memo[k];
        if (u.isNull) continue;
        if (bi[u.boxes] - u.volume < a) {
          if (u.boxes == n - 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);
}
0