結果

問題 No.626 Randomized 01 Knapsack
ユーザー te-shte-sh
提出日時 2018-01-24 12:12:58
言語 D
(dmd 2.109.1)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,285 bytes
コンパイル時間 801 ms
コンパイル使用メモリ 109,100 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-12 23:36:57
合計ジャッジ時間 2,063 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24 WA * 1
権限があれば一括ダウンロードができます

ソースコード

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