제출 #429405

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
429405		SansPapyrus683	은행 (IZhO14_bank)	Java	100 / 100	356 ms	19568 KiB

bank

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class bank {
    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer initial = new StringTokenizer(read.readLine());
        int peopleNum = Integer.parseInt(initial.nextToken());
        int noteNum = Integer.parseInt(initial.nextToken());
        int[] people = Arrays.stream(read.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] banknotes = Arrays.stream(read.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int[] leftover = new int[1 << noteNum];
        int[] peopleCovered = new int[1 << noteNum];
        Arrays.fill(leftover, -1);
        Arrays.fill(peopleCovered, -1);
        leftover[0] = 0;
        peopleCovered[0] = 0;
        for (int s = 0; s < (1 << noteNum); s++) {
            for (int last = 0; last < noteNum; last++) {
                if ((s & (1 << last)) == 0) {
                    continue;
                }
                int prev = s & ~(1 << last);
                if (peopleCovered[prev] == -1) {
                    continue;
                }

                int new_amt = leftover[prev] + banknotes[last];
                int curr_target = people[peopleCovered[prev]];
                if (new_amt < curr_target) {
                    peopleCovered[s] = peopleCovered[prev];
                    leftover[s] = new_amt;
                } else if (new_amt == curr_target) {
                    peopleCovered[s] = peopleCovered[prev] + 1;
                    leftover[s] = 0;
                }
            }
            if (peopleCovered[s] == peopleNum) {
                System.out.println("YES");
                return;
            }
        }
        System.out.println("NO");
    }
}

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