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
AC × 2
AC × 20
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