結果

問題 No.626 Randomized 01 Knapsack
ユーザー te-shte-sh
提出日時 2018-01-24 12:12:58
言語 D
(dmd 2.106.1)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,285 bytes
コンパイル時間 610 ms
コンパイル使用メモリ 94,568 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-03 18:13:46
合計ジャッジ時間 1,774 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 3 ms
4,376 KB
testcase_10 AC 3 ms
4,376 KB
testcase_11 AC 4 ms
4,380 KB
testcase_12 AC 10 ms
4,376 KB
testcase_13 AC 3 ms
4,380 KB
testcase_14 AC 4 ms
4,380 KB
testcase_15 AC 8 ms
4,376 KB
testcase_16 AC 9 ms
4,376 KB
testcase_17 AC 16 ms
4,376 KB
testcase_18 AC 5 ms
4,380 KB
testcase_19 AC 5 ms
4,376 KB
testcase_20 AC 6 ms
4,380 KB
testcase_21 AC 3 ms
4,380 KB
testcase_22 AC 6 ms
4,380 KB
testcase_23 AC 7 ms
4,384 KB
testcase_24 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.typecons;  // Tuple, Nullable, BigFlags

void readV(T...)(ref T t){auto r=readln.splitter;foreach(ref v;t){v=r.front.to!(typeof(v));r.popFront;}}
T[] readArray(T)(size_t n){auto a=new T[](n),r=readln.splitter;foreach(ref v;a){v=r.front.to!T;r.popFront;}return a;}
T[] readArrayM(T)(size_t n){auto a=new T[](n);foreach(ref v;a)v=readln.chomp.to!T;return a;}

void main()
{
  int n; long w; readV(n, w);
  VW[] vw;
  foreach (i; 0..n) {
    long vi, wi; readV(vi, wi);
    if (wi <= w) vw ~= VW(vi, wi);
  }
  n = vw.length.to!int;

  vw.sort!((a, b) => a.v.to!real/a.w > b.v.to!real/b.w);
  auto p = 0L;

  auto lowerUpper(int k, VW q)
  {
    auto l = q, u = 0.0L;
    foreach (i; k..n) {
      if (l.w + vw[i].w > w) {
        u = l.v + (w-l.w).to!real/vw[i].w * vw[i].v;
        break;
      }
      l = l + vw[i];
    }
    return tuple(l.v, max(u, l.v));
  }

  auto dfs(int k, VW q)
  {
    if (q.w > w) return;
    if (k == n-1) return;
    auto lu = lowerUpper(k, q);
    if (lu[1] < p) return;
    if (lu[0] > p) p = lu[0];
    dfs(k+1, q);
    dfs(k+1, q+vw[k]);
  }

  dfs(0, VW(0, 0));
  writeln(p);
}

struct VW
{
  long v, w;
  auto opBinary(string op: "+")(VW r) { return VW(v+r.v, w+r.w); }
}
0