結果

問題 No.27 板の準備
ユーザー te-shte-sh
提出日時 2016-09-01 23:25:35
言語 D
(dmd 2.105.2)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 1,015 bytes
コンパイル時間 678 ms
コンパイル使用メモリ 109,988 KB
実行使用メモリ 4,372 KB
最終ジャッジ日時 2023-09-02 21:51:36
合計ジャッジ時間 1,601 ms
ジャッジサーバーID
(参考情報)
judge11 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,368 KB
testcase_01 AC 1 ms
4,372 KB
testcase_02 AC 5 ms
4,368 KB
testcase_03 AC 1 ms
4,372 KB
testcase_04 AC 3 ms
4,372 KB
testcase_05 AC 3 ms
4,368 KB
testcase_06 AC 4 ms
4,372 KB
testcase_07 AC 5 ms
4,372 KB
testcase_08 AC 5 ms
4,372 KB
testcase_09 AC 5 ms
4,372 KB
testcase_10 AC 5 ms
4,372 KB
testcase_11 AC 3 ms
4,368 KB
testcase_12 AC 4 ms
4,368 KB
testcase_13 AC 3 ms
4,368 KB
testcase_14 AC 3 ms
4,368 KB
testcase_15 AC 4 ms
4,368 KB
testcase_16 AC 2 ms
4,368 KB
testcase_17 AC 5 ms
4,368 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import std.algorithm, std.array, std.container, std.range, std.bitmanip;
import std.numeric, std.math, std.bigint, std.random;
import std.string, std.conv, std.stdio, std.typecons;

void main()
{
  auto vi = readln.split.map!(to!int).array;
  vi.sort();

  auto minN = -1;
  foreach (a; 1..vi.back + 1)
    foreach (b; a..vi.back + 1)
      foreach (c; b..vi.back + 1) {
        auto n = calc(vi, [a, b, c]);
        if (n >= 0) {
          if (minN < 0)
            minN = n;
          else
            minN = min(minN, n);
        }
      }

  writeln(minN);
}

int calc(int[] vi, int[] li)
{
  auto memo = new int[](vi.back + 1);
  memo[1..$] = -1;
  
  foreach (l; li) {
    foreach (i; l..vi.back + 1) {
      if (memo[i - l] >= 0) {
        if (memo[i] < 0)
          memo[i] = memo[i - l] + 1;
        else
          memo[i] = min(memo[i], memo[i - l] + 1);
      }
    }
  }

  auto ri = vi.map!(v => memo[v]).filter!("a > 0").array;
  if (ri.length != vi.length)
    return -1;
  else
    return ri.sum;
}
0