제출 #826666

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
826666		powervic08	은행 (IZhO14_bank)	Java	100 / 100	216 ms	18972 KiB

bank

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

public class bank {

    public static void main(String[] args) throws IOException {
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(f.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] arr = new int[n];
        int[] notes = new int[m];
        st = new StringTokenizer(f.readLine());
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(f.readLine());
        for (int j = 0; j < m; j++) notes[j] = Integer.parseInt(st.nextToken());
        int[] dp = new int[1 << m];
        int[] left = new int[1 << m];
        Arrays.fill(dp, -1);
        Arrays.fill(left, -1);
        left[0] = dp[0] = 0;
        boolean good = false;
        for (int i = 0; i < 1 << m; i++) {
            for (int j = 0; j < m; j++) {
                if ((i & (1 << j)) != 0) {
                    if (dp[i ^ (1 << j)] == -1) continue;
                    int amt = notes[j] + left[i ^ (1 << j)];
                    int need = arr[dp[i ^ (1 << j)]];
                    if (amt == need) {
                        dp[i] = Math.max(dp[i], dp[i ^ (1 << j)] + 1);
                        left[i] = 0;
                    }
                    else if (amt < need) {
                        dp[i] = Math.max(dp[i], dp[i ^ (1 << j)]);
                        left[i] = amt;
                    }
                }
            }
            if (dp[i] == n) {
                out.println("YES");
                good = true;
                break;
            }
        }
        if (!good) out.println("NO");
        out.close();
        f.close();
    }

}

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