Submission #1775786
Source Code Expand
import java.util.*; class Main { static final int I=1000000000; public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n=scan.nextInt(); int ma=scan.nextInt(); int mb=scan.nextInt(); int[]d=new int[n],c=new int[n]; for(int i=0;i<n;++i){ int a=scan.nextInt(); int b=scan.nextInt(); c[i]=scan.nextInt(); d[i]=mb*a-ma*b; } int p=n/2; int[]f=new int[1<<p]; int[]fc=new int[1<<p]; int[]s=new int[1<<(n-p)]; int[]sc=new int[1<<(n-p)]; for(int i=0;i<1<<p;++i) for(int j=0;j<p;++j) if((i&1<<j)!=0){f[i]+=d[j];fc[i]+=c[j];} for(int i=1;i<1<<(n-p);++i) for(int j=0;j<n-p;++j) if((i&1<<j)!=0){s[i]+=d[p+j];sc[i]+=c[p+j];} Map<Integer,Integer>hm=new HashMap<Integer,Integer>(); for(int i=1;i<1<<(n-p);++i){ if(hm.containsKey(-s[i])) hm.put(-s[i],Math.min(hm.get(-s[i]),sc[i])); else hm.put(-s[i],sc[i]); } int m=I; for(int i=1;i<1<<(n-p);++i) if(s[i]==0)m=Math.min(m,sc[i]); for(int i=1;i<1<<p;++i){ if(f[i]==0)m=Math.min(m,fc[i]); if(hm.containsKey(f[i])) m=Math.min(m,fc[i]+hm.get(f[i])); } System.out.println(m==I?-1:m); } }
Submission Info
Submission Time | |
---|---|
Task | D - Mixing Experiment |
User | kirika_comp |
Language | Java8 (OpenJDK 1.8.0) |
Score | 400 |
Code Size | 1491 Byte |
Status | AC |
Exec Time | 541 ms |
Memory | 78044 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 | 98 ms | 20688 KB |
sample_02.txt | AC | 97 ms | 21844 KB |
subtask_1_01.txt | AC | 98 ms | 20948 KB |
subtask_1_02.txt | AC | 97 ms | 21716 KB |
subtask_1_03.txt | AC | 97 ms | 19028 KB |
subtask_1_04.txt | AC | 100 ms | 19796 KB |
subtask_1_05.txt | AC | 110 ms | 20560 KB |
subtask_1_06.txt | AC | 101 ms | 21716 KB |
subtask_1_07.txt | AC | 108 ms | 20820 KB |
subtask_1_08.txt | AC | 123 ms | 21972 KB |
subtask_1_09.txt | AC | 144 ms | 19668 KB |
subtask_1_10.txt | AC | 204 ms | 25044 KB |
subtask_1_11.txt | AC | 358 ms | 52512 KB |
subtask_1_12.txt | AC | 491 ms | 51836 KB |
subtask_1_13.txt | AC | 491 ms | 76448 KB |
subtask_1_14.txt | AC | 510 ms | 56088 KB |
subtask_1_15.txt | AC | 499 ms | 59572 KB |
subtask_1_16.txt | AC | 514 ms | 76824 KB |
subtask_1_17.txt | AC | 516 ms | 78044 KB |
subtask_1_18.txt | AC | 541 ms | 69820 KB |