結果

問題 No.626 Randomized 01 Knapsack
ユーザー te-shte-sh
提出日時 2018-07-24 18:58:55
言語 D
(dmd 2.107.1)
結果
AC  
実行時間 28 ms / 2,000 ms
コード長 1,173 bytes
コンパイル時間 870 ms
コンパイル使用メモリ 102,820 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-03 20:49:29
合計ジャッジ時間 2,376 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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