結果

問題 No.626 Randomized 01 Knapsack
コンテスト
ユーザー te-sh
提出日時 2018-07-24 18:58:55
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 23 ms / 2,000 ms
コード長 1,173 bytes
コンパイル時間 838 ms
コンパイル使用メモリ 113,280 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-13 01:33:53
合計ジャッジ時間 2,311 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}
void readS(T)(size_t n,ref T t){t=new T(n);foreach(ref v;t){auto r=rdsp;foreach(ref j;v.tupleof)pick(r,j);}}

void main()
{
  int n; long tw; readV(n, tw);
  C[] c; readS(n, c);

  c.sort!((a, b) => a.v.to!real/a.w > b.v.to!real/b.w);

  auto p = 0L;

  auto lowerUpper(int i, C s)
  {
    auto u = 0.0L;
    foreach (j; i..n) {
      if (s.w < c[j].w) {
        u = s.v + c[j].v.to!real/c[j].w*s.w;
        break;
      }
      s += c[j];
    }
    return tuple(s.v, max(u.floor.to!long, s.v));
  }

  auto dfs(int i, C s)
  {
    if (i == n) return;

    auto lu = lowerUpper(i, s);
    if (lu[1] < p) return;
    p = max(p, lu[0]);

    dfs(i+1, s);
    if (s.w >= c[i].w) dfs(i+1, s+c[i]);
  }

  dfs(0, C(0, tw));

  writeln(p);
}

struct C
{
  long v, w;
  auto opBinary(string op: "+")(C a) { return C(v+a.v, w-a.w); }
  auto opOpAssign(string op: "+")(C a) { v += a.v; w -= a.w; return this; }
}
0