Submission #1105863
Source Code Expand
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;
// cout vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
int len = v.size(); s << "\n";
for (int i = 0; i < len; ++i) {
s << v[i]; if (i < len - 1) s << "\t";
}
s << "\n"; return s;
}
// cout 2-dimentional vector
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
int len = vv.size();
for (int i = 0; i < len; ++i) { s << vv[i]; }
return s;
}
#define INF 1e9
int main() {
int n, ma, mb;
scanf("%d %d %d", &n, &ma, &mb);
vi a(n), b(n), c(n);
rep (i, n) {
scanf("%d %d %d", &a[i], &b[i], &c[i]);
}
if (n == 1) {
if (ma * b[0] == mb * a[0]) {
printf("%d\n", c[0]);
} else {
printf("-1\n");
}
return 0;
}
vvi p1(201, vi(201, INF)), p2(201, vi(201, INF));
int mid1 = n/2;
int mid2 = n - mid1;
rep (i, (1 << mid1)) {
int aa = 0;
int bb = 0;
int cost = 0;
rep (j, mid1) {
if (((i >> j)&1) == 1) {
aa += a[j];
bb += b[j];
cost += c[j];
}
}
p1[aa][bb] = min(p1[aa][bb], cost);
}
rep (i, (1 << mid2)) {
int aa = 0;
int bb = 0;
int cost = 0;
rep (j, mid2) {
if (((i >> j)&1) == 1) {
aa += a[j + mid1];
bb += b[j + mid1];
cost += c[j + mid1];
}
}
p2[aa][bb] = min(p2[aa][bb], cost);
}
int ans = INF;
rep (i, 201) {
rep (j, 201) {
if (p1[i][j] == INF) {
continue;
}
FOR (r, 1, 401) {
int ra = ma * r;
int rb = mb * r;
int i2 = ra - i;
int j2 = rb - j;
if (i2 < 0 || j2 < 0) {
continue;
}
if (i2 > 200 || j2 > 200) {
continue;
}
if (p2[i2][j2] == INF) {
continue;
}
ans = min(ans, p1[i][j] + p2[i2][j2]);
}
}
}
if (ans != INF) {
printf("%d\n", ans);
} else {
printf("-1\n");
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Mixing Experiment |
User |
tspcx |
Language |
C++14 (Clang 3.8.0) |
Score |
400 |
Code Size |
2920 Byte |
Status |
AC |
Exec Time |
128 ms |
Memory |
1144 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 |
6 ms |
1144 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
subtask_1_01.txt |
AC |
1 ms |
640 KB |
subtask_1_02.txt |
AC |
1 ms |
640 KB |
subtask_1_03.txt |
AC |
1 ms |
640 KB |
subtask_1_04.txt |
AC |
1 ms |
640 KB |
subtask_1_05.txt |
AC |
1 ms |
640 KB |
subtask_1_06.txt |
AC |
2 ms |
640 KB |
subtask_1_07.txt |
AC |
2 ms |
640 KB |
subtask_1_08.txt |
AC |
2 ms |
640 KB |
subtask_1_09.txt |
AC |
4 ms |
640 KB |
subtask_1_10.txt |
AC |
14 ms |
640 KB |
subtask_1_11.txt |
AC |
64 ms |
640 KB |
subtask_1_12.txt |
AC |
128 ms |
640 KB |
subtask_1_13.txt |
AC |
127 ms |
640 KB |
subtask_1_14.txt |
AC |
127 ms |
640 KB |
subtask_1_15.txt |
AC |
127 ms |
640 KB |
subtask_1_16.txt |
AC |
127 ms |
640 KB |
subtask_1_17.txt |
AC |
127 ms |
640 KB |
subtask_1_18.txt |
AC |
127 ms |
640 KB |