Submission #3104480


Source Code Expand

Copy
import std.stdio;
import std.conv;
import std.string;
import std.format;
import std.algorithm;
import std.typecons;
import std.array;
import std.math;

alias Tuple!(long, long) pair;

immutable long INF = pow(10, 10);

void stringsTo(string, T...)(string str, ref T t) {
  auto s = str.split();
  assert(s.length == t.length);
  foreach(ref ti; t) {
    ti = s[0].to!(typeof(ti));
    s = s[1..$];
  }
}

void meet_in_the_mid(int n, int w, pair[] vw)
{
  int s = 0;
  pair[] s1 = vw[0..n/2];
  pair[] s2 = vw[n/2..n];
  pair[] tmp_a;

  for (int bit = 0; bit < (1<<s1.length); bit++) {
    pair tmp_pair = pair(0,0);
    foreach (i; 0..s1.length) {
      if (bit & (1<<i)) {
	tmp_pair[0] += s1[i][0];
	tmp_pair[1] += s1[i][1];
      }
    }
    if (tmp_pair[1] <= w) {
      tmp_a ~= tmp_pair;
    }
  }

  sort!( (a,b) => a[0] > b[0] )(tmp_a);

  ulong ans = 0;
  for (int bit = 0; bit < (1<<s2.length); bit++) {
    pair tmp_pair = pair(0,0);
    foreach (i; 0..s2.length) {
      if (bit & (1<<i)) {
	tmp_pair[0] += s2[i][0];
	tmp_pair[1] += s2[i][1];
      }
    }

    if (tmp_pair[1] <= w) {
      pair[] x = tmp_a.find!( (e) => tmp_pair[1] + e[1] <= w );
      if (! x.empty) {
	ans = reduce!(max)([ans, x[0][0] + tmp_pair[0]]);
      }
    }
  }
  writefln("%d", ans);
}

void solve_sigma_v(int n, int w, pair[] vw, int max_v)
{
  long ans = 0;
  int max_n = n;
  long[][] dp = new long[][](max_n+1, max_n*max_v+1);

  foreach (ref l; dp) {
    fill(l, INF);
  }
  dp[0][0] = 0;

  for (long i = 0; i < n; i++) {
    long vi = vw[i][0];
    long wi = vw[i][1];

    for (long j = 0; j < vi; j++) {
      dp[i+1][j] = dp[i][j];
    }
    for (long j = vi; j < max_n * max_v; j++) {
      dp[i+1][j] = (dp[i][j] > dp[i][j-vi]+wi) ? dp[i][j-vi]+wi : dp[i][j];
    }
  }

  for (long i = 0; i < max_n * max_v; i++) {
    if (dp[n][i] <= w) ans = i;
  }
  writeln(ans);
}

void solve_sigma_w(int n, int w, pair[] vw, int max_w)
{
  long ans = 0;
  int max_n = n;
  long[][] dp = new long[][](max_n+1, max_n*max_w+1);

  for (long i = 0; i < n; i++) {
    long vi = vw[i][0];
    long wi = vw[i][1];

    for (long j = 0; j < max_n*max_w+1; j++) {
      dp[i+1][j] = dp[i][j];
    }
    for (long j = wi; j < max_n*max_w+1; j++) {
      dp[i+1][j] = (dp[i+1][j] > dp[i][j-wi]+vi) ? dp[i+1][j] : dp[i][j-wi]+vi;
    }
  }

  for (long i = 0; i < w + 1; i++) {
    ans = (ans > dp[n][i]) ? ans : dp[n][i];
  }
  writeln(ans);
}

void main()
{
  string lines;
  string buf;

  while (!stdin.eof) {
    buf = stdin.readln();
    lines ~= buf;
  }

  string[] array = splitLines(lines);

  int N, W;
  stringsTo(array[0], N, W);
  pair[] vw = new pair[N];
  int max_v, max_w;


  foreach (i; 1..N+1) {
    int v, w;
    stringsTo(array[i], v, w);
    max_v = (v > max_v) ? v : max_v;
    max_w = (w > max_w) ? w : max_w;
    pair p = pair(v, w);
    //writef("v:%d, w:%d\n", p[0], p[1]);
    vw[i-1] = p;
  }

  if (N < 31) {
    // meet in the mid
    meet_in_the_mid(N, W, vw);
  } else {
    // 01 knapsack
    if (max_v < 1001) {
      solve_sigma_v(N, W, vw, max_v);
    } else {
      solve_sigma_w(N, W, vw, max_w);
    }
  }
}

Submission Info

Submission Time
Task D - ナップサック問題
User hiroyuking
Language D (DMD64 v2.070.1)
Score 100
Code Size 3289 Byte
Status
Exec Time 178 ms
Memory 321020 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt
Subtask1 34 / 34 subtask01_0.txt, subtask01_1.txt, subtask01_10.txt, subtask01_11.txt, subtask01_12.txt, subtask01_13.txt, subtask01_14.txt, subtask01_2.txt, subtask01_3.txt, subtask01_4.txt, subtask01_5.txt, subtask01_6.txt, subtask01_7.txt, subtask01_8.txt, subtask01_9.txt, subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt
Subtask2 33 / 33 subtask02_0.txt, subtask02_1.txt, subtask02_10.txt, subtask02_11.txt, subtask02_12.txt, subtask02_13.txt, subtask02_14.txt, subtask02_2.txt, subtask02_3.txt, subtask02_4.txt, subtask02_5.txt, subtask02_6.txt, subtask02_7.txt, subtask02_8.txt, subtask02_9.txt, subtask00_sample_1.txt, subtask00_sample_3.txt
Subtask3 33 / 33 subtask03_0.txt, subtask03_1.txt, subtask03_10.txt, subtask03_11.txt, subtask03_2.txt, subtask03_3.txt, subtask03_4.txt, subtask03_5.txt, subtask03_6.txt, subtask03_7.txt, subtask03_8.txt, subtask03_9.txt, subtask00_sample_1.txt, subtask00_sample_4.txt
Case Name Status Exec Time Memory
subtask00_sample_1.txt 1 ms 256 KB
subtask00_sample_2.txt 5 ms 256 KB
subtask00_sample_3.txt 1 ms 256 KB
subtask00_sample_4.txt 1 ms 256 KB
subtask01_0.txt 4 ms 256 KB
subtask01_1.txt 4 ms 256 KB
subtask01_10.txt 4 ms 256 KB
subtask01_11.txt 4 ms 256 KB
subtask01_12.txt 5 ms 256 KB
subtask01_13.txt 4 ms 256 KB
subtask01_14.txt 4 ms 256 KB
subtask01_2.txt 4 ms 256 KB
subtask01_3.txt 4 ms 256 KB
subtask01_4.txt 4 ms 256 KB
subtask01_5.txt 17 ms 1788 KB
subtask01_6.txt 4 ms 256 KB
subtask01_7.txt 4 ms 256 KB
subtask01_8.txt 5 ms 256 KB
subtask01_9.txt 4 ms 256 KB
subtask02_0.txt 173 ms 318332 KB
subtask02_1.txt 173 ms 315388 KB
subtask02_10.txt 173 ms 316412 KB
subtask02_11.txt 174 ms 318972 KB
subtask02_12.txt 171 ms 314748 KB
subtask02_13.txt 2 ms 764 KB
subtask02_14.txt 172 ms 316540 KB
subtask02_2.txt 172 ms 315388 KB
subtask02_3.txt 173 ms 316540 KB
subtask02_4.txt 174 ms 317308 KB
subtask02_5.txt 175 ms 321020 KB
subtask02_6.txt 172 ms 314236 KB
subtask02_7.txt 171 ms 315516 KB
subtask02_8.txt 173 ms 316796 KB
subtask02_9.txt 173 ms 316156 KB
subtask03_0.txt 174 ms 316412 KB
subtask03_1.txt 176 ms 318332 KB
subtask03_10.txt 175 ms 315260 KB
subtask03_11.txt 1 ms 764 KB
subtask03_2.txt 173 ms 316028 KB
subtask03_3.txt 174 ms 314748 KB
subtask03_4.txt 175 ms 317308 KB
subtask03_5.txt 172 ms 313084 KB
subtask03_6.txt 174 ms 315132 KB
subtask03_7.txt 178 ms 319868 KB
subtask03_8.txt 177 ms 314620 KB
subtask03_9.txt 178 ms 318588 KB