제출 #392142

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
392142		TruaShamu	은행 (IZhO14_bank)	Java	71 / 100	1066 ms	47164 KiB

bank

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.StringTokenizer;

public class bank {
    public static int N, M, s, l;
    public static int[] A;
    public static BitSet[] ct = new BitSet[(1 << 20)];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        //@TODO READ SALARY.
        A = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }


        //@TODO READ PAYNOTES
        int[] B = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }

        ArrayList<Integer>[] sum = new ArrayList[20001];
        for (int i = 0; i < sum.length; i++) {
            sum[i] = new ArrayList<>();
        }

        for (int mask = 0; mask < (1 << M); ++mask) {
            int cur = 0;
            for (int i = 0; i < M; ++i) {
                if ((mask & (1 << i)) > 0) {
                    cur += B[i];
                }
            }
            sum[cur].add(mask);
        }
        ArrayList<Integer>[] dp = new ArrayList[N + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = new ArrayList<>();
        }
        dp[0].add(0);
        boolean f = false;
        for (int i = 0; i < N; ++i) {
            boolean[] vis = new boolean[1 << M];
            f = false;
            for (int mask : sum[A[i]]) {
                for (int pmask : dp[i]) {
                    if ((mask & pmask) <= 0 && !vis[mask | pmask]) {
                        vis[mask | pmask] = true;
                        dp[i + 1].add(mask | pmask);
                        f = true;
                    }
                }
            }
        }
        System.out.println(f ? "YES" : "NO");
    }
}

컴파일 시 표준 에러 (stderr) 메시지

Note: bank.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

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