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 |
|
|
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 |