Submission #2209709
Source Code Expand
#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
template<typename T>
void print_to(std::ostream &os,const char *,const char *tail,const T &fst){
os<<fst<<tail;
}
template<typename Fst,typename... Rst>
void print_to(std::ostream &os,const char *del,const char *tail,const Fst &fst,const Rst &... rst){
os<<fst<<del;
print_to(os,del,tail,rst...);
}
template<typename Iter>
void print_to_(std::ostream &os,const char *del,const char *tail,Iter bgn,Iter end){
for(Iter it=bgn;it!=end;){
os<<*it;
if(++it!=end)os<<del;
else os<<tail;
}
}
template<typename Fst,typename... Rst>
void println(const Fst &fst,const Rst &... rst){
print_to(std::cout,"\n","\n",fst,rst...);
}
template<typename Fst,typename... Rst>
void print(const Fst &fst,const Rst &... rst){
print_to(std::cout," ","\n",fst,rst...);
}
template<typename Iter>
void println_(Iter bgn,Iter end){
print_to_(std::cout," ","\n",bgn,end);
}
using namespace std;
//const ll MOD=(ll)1e9+7;
const ll inf=(ll)1e14;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};
int n,m,h,w;
string s;
int ma,mb;
int a[41],b[41],c[41];
ll dp[41][401][401];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.precision(10);
cout<<fixed;
#ifdef LOCAL_DEFINE
FILE *stream1;
//FILE *stream2;
stream1=freopen("in","r",stdin);
//stream2=freopen("out","w",stdout);
if(stream1==NULL)return 0;
//if(stream2==NULL)return 0;
#endif
cin>>n>>ma>>mb;
int suma=0,sumb=0;
for(int i=0;i<n;i++){
cin>>a[i]>>b[i]>>c[i];
suma+=a[i];
sumb+=b[i];
}
ll ans=inf;
int nowma=0,nowmb=0;
while(nowma+ma<=suma && nowmb+mb<=sumb){
nowma+=ma;nowmb+=mb;
for(int i=0;i<=n;i++){
for(int j=0;j<=nowma;j++){
for(int k=0;k<=nowmb;k++){
dp[i][j][k]=inf;
}
}
}
dp[0][0][0]=0;
for(int i=0;i<n;i++){
for(int j=0;j<=nowma;j++){
for(int k=0;k<=nowmb;k++){
if(j+a[i]<=nowma && k+b[i]<=nowmb){
dp[i+1][j+a[i]][k+b[i]]=min(dp[i+1][j+a[i]][k+b[i]],dp[i][j][k]+c[i]);
}
dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k]);
}
}
}
ans=min(ans,dp[n][nowma][nowmb]);
}
if(ans==inf)print(-1);
else print(ans);
#ifdef LOCAL_DEFINE
cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
fclose(stream1);
//fclose(stream2);
#endif
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Mixing Experiment |
User |
aim_cpo |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
2529 Byte |
Status |
AC |
Exec Time |
487 ms |
Memory |
50816 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 |
2 ms |
2304 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
subtask_1_01.txt |
AC |
2 ms |
6528 KB |
subtask_1_02.txt |
AC |
2 ms |
2432 KB |
subtask_1_03.txt |
AC |
2 ms |
6400 KB |
subtask_1_04.txt |
AC |
4 ms |
12672 KB |
subtask_1_05.txt |
AC |
5 ms |
17152 KB |
subtask_1_06.txt |
AC |
7 ms |
23168 KB |
subtask_1_07.txt |
AC |
9 ms |
25088 KB |
subtask_1_08.txt |
AC |
11 ms |
29312 KB |
subtask_1_09.txt |
AC |
24 ms |
35584 KB |
subtask_1_10.txt |
AC |
32 ms |
42112 KB |
subtask_1_11.txt |
AC |
26 ms |
48000 KB |
subtask_1_12.txt |
AC |
487 ms |
50816 KB |
subtask_1_13.txt |
AC |
21 ms |
49664 KB |
subtask_1_14.txt |
AC |
47 ms |
50688 KB |
subtask_1_15.txt |
AC |
50 ms |
50688 KB |
subtask_1_16.txt |
AC |
35 ms |
49920 KB |
subtask_1_17.txt |
AC |
38 ms |
50816 KB |
subtask_1_18.txt |
AC |
56 ms |
50688 KB |