Submission #781084

#	Time	Username	Problem	Language	Result	Execution time	Memory
781084		sushikid	Bank (IZhO14_bank)	Java	100 / 100	330 ms	40832 KiB

bank

import java.util.*;
import java.io.*;

public class bank {
    public static void main(String[] args) throws IOException{
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(r.readLine());
        int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken());
        int[] salarys = new int[n];
        int[] banknotes=  new int[m];
        st = new StringTokenizer(r.readLine());
        for (int i = 0; i < n; i++) {
            salarys[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(r.readLine());
        for (int i = 0; i < m; i++) {
            banknotes[i] = Integer.parseInt(st.nextToken());
        }
        int[][] dp = new int[1 << m][2]; //[cur i you're trying to complete, cur sum]
        for (int i = 1; i < (1 << m); i++) {
            int max_idx = 0;
            int sum = 0;
            for (int j = 0; j < m; j++) {
                if((i & (1 << j)) != 0){
                    int idx = i - (1 << j);
                    int temp_idx = dp[idx][0];
                    int temp_sum = dp[idx][1];
                    if(dp[idx][1] + banknotes[j] < salarys[dp[idx][0]]){
                        temp_sum += banknotes[j];
                    }
                    else if(dp[idx][1] + banknotes[j] == salarys[dp[idx][0]]){
                        temp_idx ++;
                        temp_sum = 0;
                    }
                    else{
                        continue;
                    }
                    if(max_idx < temp_idx){
                        max_idx = temp_idx;
                        sum = temp_sum;
                    }
                    else if(max_idx == temp_idx){
                        sum = temp_sum;
                    }
                }
            }
            dp[i][0] = max_idx;
            dp[i][1] = sum;
            if(max_idx == n){
                pw.println("YES");
                pw.close();
                return;
            }
        }
        pw.println("NO");
        pw.close();
    }
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29