Submission #1230317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230317		franktastic	Bank (IZhO14_bank)	Java	52 / 100	1097 ms	38816 KiB

bank

import java.io.*;
import java.lang.*;
import java.math.*;
import java.util.*;

public class bank { 
    static FastInputReader in = new FastInputReader(); 
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    public static void main(String[] args) throws Exception {
        int n = in.nextInt();
        int m = in.nextInt();
        int[] a = in.nextArrayInt(n);
        int[] b = in.nextArrayInt(m);

        int maxTarget = a[0];
        for (int i=1; i<n; i++) {
            maxTarget = Math.max(a[i], maxTarget);
        }
        ArrayList<Integer>[][] knapsack = new ArrayList[m+1][maxTarget+1];
        for (int i=0; i<m+1; i++) {
            for (int j=0; j<knapsack[0].length; j++) {
                knapsack[i][j] = new ArrayList<Integer>();
            }
        }
        knapsack[0][0].add(0);
        for (int i=1; i<=m; i++) {
            for (int j=0; j<knapsack[0].length; j++) {
                knapsack[i][j].addAll(knapsack[i-1][j]); // dont pick
                if (j >= b[i-1]) {
                    for (int k : knapsack[i-1][j-b[i-1]]) {
                        knapsack[i][j].add(k | (1<<(i-1)));
                    }
                }
            }
        }
        
        //System.out.println(knapsack[5][8]);
        var dp = new boolean[n+1][1<<m];
        dp[0][0] = true;
        for (int i=1; i<=n; i++) {
            //System.out.println(knapsack[5][8]);
            for (int j=1; j<(1<<m); j++) {
                for (int k : knapsack[m][a[i-1]]) { // possible candidates to cover person i
                    //System.out.println("checking: " + k);
                    if ((j & k) == k && dp[i-1][j^k]) {
                        dp[i][j] = true;
                        break;
                    }
                }
            }
        }
        
        for (int j=0; j<(1<<m); j++) {
            if (dp[n][j]) {
                System.out.println("YES");
                return;
            }
        }
        System.out.println("NO");
    }

























    // ==================================================================
    // ======================== Boilerplate Code ========================
    // ==================================================================
    static class FastInputReader {
        private static final int BUF_SIZE = 1 << 20; // 1 MB buffer
        private final InputStream in = System.in;
        private final byte[] buf = new byte[BUF_SIZE];
        private int ptr = 0, buflen = 0;

        public FastInputReader() { }

        private final byte read() throws IOException {
            if (ptr >= buflen) {
                buflen = in.read(buf, 0, BUF_SIZE);
                ptr = 0;
                if (buflen == -1) return -1;
            }
            return buf[ptr++];
        }

        public final int nextInt() throws IOException {
            byte b;
            // skip whitespace
            do { b = read(); } while (b != -1 && b <= ' ');
            if (b == -1) throw new IOException("End of input");
            // sign
            boolean neg = (b == '-');
            if (neg) b = read();
            // parse digits
            int x = 0;
            while (b >= '0' && b <= '9') {
                x = x * 10 + (b - '0');
                b = read();
            }
            return neg ? -x : x;
        }

        public final long nextLong() throws IOException {
            byte b;
            do { b = read(); } while (b != -1 && b <= ' ');
            if (b == -1) throw new IOException("End of input");
            boolean neg = (b == '-');
            if (neg) b = read();
            long x = 0;
            while (b >= '0' && b <= '9') {
                x = x * 10 + (b - '0');
                b = read();
            }
            return neg ? -x : x;
        }

        public final double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public final BigInteger nextBigInteger() throws IOException {
            return new BigInteger(next());
        }

        public final BigDecimal nextBigDecimal() throws IOException {
            return new BigDecimal(next());
        }

        public final char nextChar() throws IOException {
            byte b;
            do { b = read(); } while (b != -1 && b <= ' ');
            if (b == -1) throw new IOException("End of input");
            return (char) b;
        }

        public final String next() throws IOException {
            byte b;
            do { b = read(); } while (b != -1 && b <= ' ');
            if (b == -1) return null;
            StringBuilder sb = new StringBuilder();
            do {
                sb.append((char)b);
                b = read();
            } while (b != -1 && b > ' ');
            return sb.toString();
        }

        public final String nextLine() throws IOException {
            StringBuilder sb = new StringBuilder();
            byte b;
            while ((b = read()) != -1 && b != '\n') {
                if (b != '\r') sb.append((char)b);
            }
            return sb.toString();
        }

        public final int[] nextArrayInt(int n) throws IOException {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) arr[i] = nextInt();
            return arr;
        }

        public final long[] nextArrayLong(int n) throws IOException {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) arr[i] = nextLong();
            return arr;
        }

        public final double[] nextArrayDouble(int n) throws IOException {
            double[] arr = new double[n];
            for (int i = 0; i < n; i++) arr[i] = nextDouble();
            return arr;
        }

        public final char[] nextArrayChar(int n) throws IOException {
            // reads next token and returns its chars
            return next().toCharArray();
        }

        public final BigInteger[] nextArrayBigInteger(int n) throws IOException {
            BigInteger[] arr = new BigInteger[n];
            for (int i = 0; i < n; i++) arr[i] = nextBigInteger();
            return arr;
        }

        public final BigDecimal[] nextArrayBigDecimal(int n) throws IOException {
            BigDecimal[] arr = new BigDecimal[n];
            for (int i = 0; i < n; i++) arr[i] = nextBigDecimal();
            return arr;
        }

        public final String[] nextArrayString(int n) throws IOException {
            String[] arr = new String[n];
            for (int i = 0; i < n; i++) arr[i] = next();
            return arr;
        }
    }

    static long gcd(long x, long y) {
        x = Math.abs(x);
        y = Math.abs(y);
        
        while (y != 0) {
            long c = x % y;
            x = y;
            y = c;
        }
        return x;
    }

    public static int gcd(int x, int y) {
        x = Math.abs(x);
        y = Math.abs(y);
        
        while (y != 0) {
            int c = x % y;
            x = y;
            y = c;
        }
        return x;
    }
    

    public static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }

    public static int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }

    // Returns the next permutation of [start, end) in ascending. 
    // Will return false when there are none left. Can handle duplicates just fine.
    public static boolean nextPermutation(int[] nums, int start, int end) { 
        for (int i=end-2; i>=start; i--) {
            if (nums[i] < nums[i+1]) {
                int replacement = nums[i+1]; 
                int replacementIndex = i+1;
                for (int j=i+2; j<end; j++) {
                    if (nums[j] > nums[i] && nums[j] <= replacement) {
                        replacement = nums[j];
                        replacementIndex = j;
                    }
                }
                swap(nums, i, replacementIndex);
                reverse(nums, i+1, end);  // sort the tail, which is conveniently reversed
                return true;
            }
        }
        return false;
    }

    public static void reverse(int[] nums, int start, int end) { // swaps [start, end)
        end--;
        while (start < end) {
            swap(nums, start, end);
            start++; 
            end--;
        }
    }
    
    public static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    // Fisher-Yates shuffle algorithm - Can be used to avoid quicksort's O(N^2) worst case
    public static void arrayShuffle(int[] arr) { 
        Random r = new Random();
        for (int i=arr.length-1; i>=1; i--) {
            int inx = r.nextInt(i+1);
            int t = arr[inx];
            arr[inx] = arr[i];
            arr[i] = t;
        }
    }

    // Fisher-Yates shuffle algorithm - Can be used to avoid quicksort's O(N^2) worst case
    public static void arrayShuffle(long[] arr) { 
        Random r = new Random();
        for (int i=arr.length-1; i>=1; i--) {
            int inx = r.nextInt(i+1);
            long t = arr[inx];
            arr[inx] = arr[i];
            arr[i] = t;
        }
    }

    // Fisher-Yates shuffle algorithm - Can be used to avoid quicksort's O(N^2) worst case
    public static void arrayShuffle(double[] arr) { 
        Random r = new Random();
        for (int i=arr.length-1; i>=1; i--) {
            int inx = r.nextInt(i+1);
            double t = arr[inx];
            arr[inx] = arr[i];
            arr[i] = t;
        }
    }

    static long modpow(long a, long b, long mod) { // a^b % mod (note: 0^0 returns 1)
        a %= mod;
        long ans = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                ans = (ans * a) % mod;
            }
            b >>= 1;
            a = a * a % mod;
        }
        return ans;
    }

    // Much faster adjacency List - backed by only primitive arrays
    public static int[][] buildGraphFast(int n, int[][] edges, boolean bidirectional) {
        var g = new int[n][];
        var outDegree = new int[n];
        for (int[] e : edges) {
            outDegree[e[0]]++;
            if (bidirectional) {
                outDegree[e[1]]++;
            }
        }
        for (int i=0; i<n; i++) {
            g[i] = new int[outDegree[i]];
        }
        
        for (int[] e : edges) {
            int u = e[0];
            int v = e[1];
            g[u][--outDegree[u]] = v;
            if (bidirectional) {
                g[v][--outDegree[v]] = u;
            }
        }
        return g;
    }
        
    // WARNING: Only works for prime MOD. 
    public static long modInverse(long a, long mod) {  
        return modpow(a, mod-2, mod); // fermat's little theorem a^(p-1) = 1(mod p)
    }

    public static int[] concat(int[] a, int[] b) {
        int[] result = new int[a.length + b.length];
        System.arraycopy(a, 0, result, 0, a.length);
        System.arraycopy(b, 0, result, a.length, b.length);
        return result;
    }

    public static long[] concat(long[] a, long[] b) {
        long[] result = new long[a.length + b.length];
        System.arraycopy(a, 0, result, 0, a.length);
        System.arraycopy(b, 0, result, a.length, b.length);
        return result;
    }

    public static String[] concat(String[] a, String[] b) {
        String[] result = new String[a.length + b.length];
        System.arraycopy(a, 0, result, 0, a.length);
        System.arraycopy(b, 0, result, a.length, b.length);
        return result;
    }

    public static double[] concat(double[] a, double[] b) {
        double[] result = new double[a.length + b.length];
        System.arraycopy(a, 0, result, 0, a.length);
        System.arraycopy(b, 0, result, a.length, b.length);
        return result;
    }
    
    public static char[] concat(char[] a, char[] b) {
        char[] result = new char[a.length + b.length];
        System.arraycopy(a, 0, result, 0, a.length);
        System.arraycopy(b, 0, result, a.length, b.length);
        return result;
    }

    public static int min(int... x) { // Assumes non-zero arguments
        int m = x[0];
        for (int xx : x) {
            if (m > xx) {
                m = xx;
            }
        }
        return m;
    }

    public static long min(long... x) { // Assumes non-zero arguments
        long m = x[0];
        for (long xx : x) {
            if (m > xx) {
                m = xx;
            }
        }
        return m;
    }

    public static double min(double... x) { // Assumes non-zero arguments
        double m = x[0];
        for (double xx : x) {
            if (m > xx) {
                m = xx;
            }
        }
        return m;
    }

    public static char min(char... x) { // Assumes non-zero arguments
        char m = x[0];
        for (char xx : x) {
            if (m > xx) {
                m = xx;
            }
        }
        return m;
    }

    public static String min(String... x) { // Assumes non-zero arguments
        String m = x[0];
        for (String xx : x) {
            if (m.compareTo(xx) > 0) {
                m = xx;
            }
        }
        return m;
    }

    public static int max(int... x) { // Assumes non-zero arguments
        int m = x[0];
        for (int xx : x) {
            if (m < xx) {
                m = xx;
            }
        }
        return m;
    }

    public static long max(long... x) { // Assumes non-zero arguments
        long m = x[0];
        for (long xx : x) {
            if (m < xx) {
                m = xx;
            }
        }
        return m;
    }

    public static double max(double... x) { // Assumes non-zero arguments
        double m = x[0];
        for (double xx : x) {
            if (m < xx) {
                m = xx;
            }
        }
        return m;
    }

    public static char max(char... x) { // Assumes non-zero arguments
        char m = x[0];
        for (char xx : x) {
            if (m < xx) {
                m = xx;
            }
        }
        return m;
    }

    public static String max(String... x) { // Assumes non-zero arguments
        String m = x[0];
        for (String xx : x) {
            if (m.compareTo(xx) < 0) {
                m = xx;
            }
        }
        return m;
    }
}

Compilation message (stderr)

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

=======

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