Submission #593809

#	Time	Username	Problem	Language	Result	Execution time	Memory
593809		DylanSmith	Bank (IZhO14_bank)	Java	100 / 100	284 ms	21244 KiB

bank

import java.util.*;
import java.io.*;
public class bank {
    public static void main(String[] args) throws IOException {
        Reader in = new Reader();
        PrintWriter out = new PrintWriter(System.out);
        
        int N = in.nextInt(), M = in.nextInt();
        int[] arr = new int[N], val = new int[M];
        for (int i = 0; i < N; i++) {
            arr[i] = in.nextInt();
        }
        for (int i = 0; i < M; i++) {
            val[i] = in.nextInt();
        }
        boolean[] dp = new boolean[1 << M];
        dp[0] = true;
        int[] pos = new int[1 << M], amt = new int[1 << M];
        boolean res = false;
        for (int i = 1; i < 1 << M; i++) {
            for (int j = 0; j < M; j++) {
                if ((i & 1 << j) > 0) {
                    if (dp[i ^ 1 << j]) {
                        if (pos[i ^ 1 << j] < N && amt[i ^ 1 << j] + val[j] <= arr[pos[i ^ 1 << j]]) {
                            dp[i] = true;
                            pos[i] = pos[i ^ 1 << j];
                            amt[i] = amt[i ^ 1 << j] + val[j];
                            if (amt[i] == arr[pos[i]]) {
                                pos[i]++;
                                amt[i] = 0;
                            }
                        }
                    }
                }
            }
            if (dp[i] && pos[i] == N) {
                res = true;
            }
        }
        out.println(res ? "YES" : "NO");
        
        out.close();
    }
    static class Reader {
        BufferedInputStream in;
        public Reader() {
            in = new BufferedInputStream(System.in);
        }
        public String nextLine() throws IOException {
            int c;
            StringBuilder sb = new StringBuilder("");
            while ((c = in.read()) != '\n')
                sb.append((char)(c));
            return sb.toString();
        }
        public String next() throws IOException {
            int c;
            StringBuilder sb = new StringBuilder("");
            while ((c = in.read()) != ' ' && c != '\n')
                sb.append((char)(c));
            return sb.toString();
        }
        public int nextInt() throws IOException {
            return (int)nextLong();
        }
        public long nextLong() throws IOException {
            int c;
            long res = 0;
            boolean start = false, negative = false;
            while ((c = in.read()) != ' ' && c != '\n' || !start)
                if (c >= '0' && c <= '9' || c == '-') {
                    start = true;
                    if (c == '-')
                        negative = true;
                    else
                        res = res * 10 + c - '0';
                }
            return res * (negative ? -1 : 1);
        }
    }
    public static void sort(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            list.add(i);
        }
        Collections.sort(list);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
    }
}

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