Submission #3051514
Source Code Expand
#include <bits/stdc++.h>
#include <string.h>
using namespace std;
///////////////////////////////////////////
//const long long int INF = 1000000000000000000LL;
const long long int INF = 1000000;
using ll = long long int;
using vi = vector<int>;
using Vi = vector<long long int>;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(int i=0;i<N;i++)
auto max(auto x,auto y){if(x>y){return x;}else{return y;}}
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return 1; } return 0; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return 1; } return 0; }
template<class T>T sqar(T x){ return x*x; }
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype( v[0])>()) //降順でVをソート
///////////////////////////////////////////
ll n,ma,mb;
vi a,b,c;
ll dp[50][401][401]; //dp[i][j][k] := i番目まででaがj,bがkとなる最小の値段
/*
* dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j-a[i]][
*/
void cal(int num,int x,int y){
// cout<<"num,x,y : "<<num<<" , "<<x<<" , "<<y<<" , "<<dp[num][x][y]<<endl;
if(num>=n) {
}else if(dp[num][x][y]==INF){
}else{
chmin(dp[num+1][x+a[num]][y+b[num]],dp[num][x][y]+c[num]);
chmin(dp[num+1][x][y],dp[num][x][y]);
cal(num+1,x,y);
cal(num+1,x+a[num],y+b[num]);
}
}
int main(){
cin>>n>>ma>>mb;
int aa,bb,cc;
rep(i,50)rep(j,401)rep(k,401)dp[i][j][k]=INF;
dp[0][0][0]=0;
//ll key = 0;
rep(i,n){
cin>>aa>>bb>>cc;
a.pb(aa);
//key+=aa;
b.pb(bb);
c.pb(cc);
}
cal(0,0,0);
ll ans = INF;
for(int i =1;i<50;i++){
if(ma*i>490 || mb*i>490){
break;
}else{
chmin(ans,dp[n][ma*i][mb*i]);
}
}
if(ans==INF){
cout<<-1<<endl;
}else{
cout<<ans<<endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Mixing Experiment |
User |
emile11235 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1978 Byte |
Status |
TLE |
Exec Time |
2104 ms |
Memory |
63104 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
19 ms |
63104 KB |
sample_02.txt |
AC |
19 ms |
63104 KB |
subtask_1_01.txt |
AC |
19 ms |
63104 KB |
subtask_1_02.txt |
AC |
19 ms |
63104 KB |
subtask_1_03.txt |
AC |
19 ms |
63104 KB |
subtask_1_04.txt |
AC |
18 ms |
63104 KB |
subtask_1_05.txt |
AC |
19 ms |
63104 KB |
subtask_1_06.txt |
AC |
21 ms |
63104 KB |
subtask_1_07.txt |
AC |
35 ms |
63104 KB |
subtask_1_08.txt |
AC |
82 ms |
63104 KB |
subtask_1_09.txt |
AC |
1987 ms |
63104 KB |
subtask_1_10.txt |
TLE |
2104 ms |
63104 KB |
subtask_1_11.txt |
TLE |
2104 ms |
63104 KB |
subtask_1_12.txt |
TLE |
2104 ms |
63104 KB |
subtask_1_13.txt |
TLE |
2104 ms |
63104 KB |
subtask_1_14.txt |
TLE |
2104 ms |
63104 KB |
subtask_1_15.txt |
TLE |
2104 ms |
63104 KB |
subtask_1_16.txt |
TLE |
2104 ms |
63104 KB |
subtask_1_17.txt |
TLE |
2104 ms |
63104 KB |
subtask_1_18.txt |
TLE |
2104 ms |
63104 KB |