Submission #2241367
Source Code Expand
#include <iostream> #include <algorithm> using namespace std; struct yakuhin { int a; int b; int c; }; class Less{ public: bool operator()(const struct yakuhin& left, const struct yakuhin& right){ return (left.a==right.a)?(left.b<right.b):(left.a<right.a); } }; struct yakuhin zenhan[1048576]; struct yakuhin kouhan[1048576]; int main(){ int n,Ma,Mb; cin >> n >> Ma >> Mb; struct yakuhin y[40]; if(Ma>=Mb){ for(int i=0;i<n;i++){ cin >> y[i].a >> y[i].b >> y[i].c; } }else{ for(int i=0;i<n;i++){ cin >> y[i].b >> y[i].a >> y[i].c; } int tmp; tmp=Ma; Ma=Mb; Mb=tmp; } for(int i=0;i<(1<<((n+1)/2));i++){ zenhan[i].a = zenhan[i].b = zenhan[i].c = 0; for(int j=0;j<(n+1)/2;j++){ if(i&(1<<j)){ zenhan[i].a += y[j].a; zenhan[i].b += y[j].b; zenhan[i].c += y[j].c; } } } for(int i=0;i<(1<<(n/2));i++){ kouhan[i].a = kouhan[i].b = kouhan[i].c = 0; for(int j=0;j<n/2;j++){ if(i&(1<<j)){ kouhan[i].a += y[j+(n+1)/2].a; kouhan[i].b += y[j+(n+1)/2].b; kouhan[i].c += y[j+(n+1)/2].c; } } } sort(zenhan,zenhan+(1<<((n+1)/2)),Less()); sort(kouhan,kouhan+(1<<(n/2)),Less()); int ans=1000000000; int k; for(int i=1;i<=10*n/Ma;i++){ k=(1<<(n/2))-1; for(int j=0;j<(1<<((n+1)/2));j++){ if(zenhan[j].a>Ma*i) break; while(zenhan[j].a+kouhan[k].a>Ma*i){ k--; if(k<0) break; } if(k<0) break; if(zenhan[j].a+kouhan[k].a==Ma*i){ while(zenhan[j].b+kouhan[k].b>Mb*i){ k--; if(zenhan[j].a+kouhan[k].a!=Ma*i||k<0) break; } if(k<0) break; if(zenhan[j].a+kouhan[k].a==Ma*i&&zenhan[j].b+kouhan[k].b==Mb*i){ ans=((zenhan[j].c+kouhan[k].c<ans)?(zenhan[j].c+kouhan[k].c):ans); } } } } if(ans==1000000000) cout << -1 << endl; else cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Mixing Experiment |
User | yamunaku |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2050 Byte |
Status | WA |
Exec Time | 1265 ms |
Memory | 24832 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 | 2 ms | 2304 KB |
sample_02.txt | AC | 2 ms | 2304 KB |
subtask_1_01.txt | AC | 2 ms | 2304 KB |
subtask_1_02.txt | AC | 1 ms | 2304 KB |
subtask_1_03.txt | AC | 1 ms | 2304 KB |
subtask_1_04.txt | AC | 1 ms | 2304 KB |
subtask_1_05.txt | AC | 1 ms | 2304 KB |
subtask_1_06.txt | AC | 2 ms | 2304 KB |
subtask_1_07.txt | AC | 2 ms | 2304 KB |
subtask_1_08.txt | AC | 2 ms | 2304 KB |
subtask_1_09.txt | WA | 8 ms | 2432 KB |
subtask_1_10.txt | AC | 50 ms | 3072 KB |
subtask_1_11.txt | AC | 185 ms | 16640 KB |
subtask_1_12.txt | AC | 1265 ms | 24832 KB |
subtask_1_13.txt | AC | 371 ms | 24832 KB |
subtask_1_14.txt | WA | 400 ms | 24832 KB |
subtask_1_15.txt | WA | 378 ms | 24832 KB |
subtask_1_16.txt | AC | 387 ms | 24832 KB |
subtask_1_17.txt | AC | 374 ms | 24832 KB |
subtask_1_18.txt | AC | 396 ms | 24832 KB |