Submission #1611083


Source Code Expand

import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.bitmanip;  // BitArray

static inf = 10 ^^ 8;

void main()
{
  auto rd1 = readln.split, n = rd1[0].to!size_t, ma = rd1[1].to!int, mb = rd1[2].to!int;
  auto d = new Chemical[](n);
  foreach (i; 0..n) {
    auto rd2 = readln.split.to!(int[]), a = rd2[0], b = rd2[1], c = rd2[2];
    d[i] = Chemical(a, b, c);
  }

  auto n1 = (n+1)/2, n2 = n-n1;

  auto a2s = d[n1..$].map!"a.a".sum, da2 = (a2s+ma-1)/ma;
  auto b2s = d[n1..$].map!"a.b".sum, db2 = (b2s+mb-1)/mb;

  auto e = new Chemical[][][](ma, mb, da2+db2+1);
  foreach (i; 0..ma)
    foreach (j; 0..mb)
      e[i][j][] = Chemical(-1, -1, inf);
    
  foreach (i; 1..1<<n2) {
    auto f = d[n1..$].indexed(i.bitsSet).sum;
    auto ia = f.a % ma, ib = f.b % mb, id = (f.b+mb-1)/mb - (f.a+ma-1)/ma + da2;
    if (f.c < e[ia][ib][id].c) e[ia][ib][id] = f;
  }

  auto ans = inf;
  foreach (i; 0..1<<n1) {
    auto f = d.indexed(i.bitsSet).sum;
    if (f.a > 0 && f.b > 0 && f.a % ma == 0 && f.b % mb == 0 && f.a/ma == f.b/mb) {
      ans = min(ans, f.c);
    } else {
      auto ia = (ma - f.a % ma) % ma, ib = (mb - f.b % mb) % mb, id = f.a/ma - f.b/mb + da2;
      if (0 <= id && id <= da2 + db2)
        ans = min(ans, f.c + e[ia][ib][id].c);
    }
  }

  writeln(ans == inf ? -1 : ans);
}

struct Chemical
{
  int a, b, c;
  auto opBinary(string op: "+")(Chemical rhs) { return Chemical(a + rhs.a, b + rhs.b, c + rhs.c); }
}

Submission Info

Submission Time
Task D - Mixing Experiment
User tesh
Language D (DMD64 v2.070.1)
Score 400
Code Size 1506 Byte
Status AC
Exec Time 1066 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 2
AC × 20
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 1 ms 256 KB
subtask_1_03.txt AC 1 ms 256 KB
subtask_1_04.txt AC 1 ms 256 KB
subtask_1_05.txt AC 1 ms 256 KB
subtask_1_06.txt AC 1 ms 256 KB
subtask_1_07.txt AC 2 ms 256 KB
subtask_1_08.txt AC 3 ms 256 KB
subtask_1_09.txt AC 14 ms 256 KB
subtask_1_10.txt AC 88 ms 256 KB
subtask_1_11.txt AC 511 ms 256 KB
subtask_1_12.txt AC 1065 ms 256 KB
subtask_1_13.txt AC 1066 ms 256 KB
subtask_1_14.txt AC 1061 ms 256 KB
subtask_1_15.txt AC 1060 ms 256 KB
subtask_1_16.txt AC 1065 ms 256 KB
subtask_1_17.txt AC 1061 ms 256 KB
subtask_1_18.txt AC 1060 ms 256 KB