Submission #1207861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207861		uranium235	Bank (IZhO14_bank)	Java	100 / 100	178 ms	20432 KiB

bank

//package ojuz;

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

public class bank {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] first = reader.readLine().split(" ");
        int n = Integer.parseInt(first[0]), m = Integer.parseInt(first[1]);

        int[] salary = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] notes = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int[] dp = new int[1 << m];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        int[] pd = new int[1 << m];

        for (int i = 1; i < (1 << m); i++) {
            for (int j = i; j > 0; j -= j & -j) {
                int k = j & -j;
                int idx = Integer.numberOfTrailingZeros(k);
                if (dp[i ^ k] == -1) continue;
                int cmp = Integer.compare(pd[i ^ k] + notes[idx], salary[dp[i ^ k]]);
                int newDp = dp[i ^ k], newPd = pd[i ^ k];
                if (cmp == 0) {
                    // adding this note completes a persons salary
                    newDp++;
                    newPd = 0;
                } else if (cmp < 0) {
                    // adding this note partially completes a persons salary
                    newPd += notes[idx];
                }

                // same prefix done, maximize part done
                if (newDp == dp[i]) pd[i] = Math.max(pd[i], newPd);
                // greater prefix done
                else if (newDp > dp[i]) {
                    dp[i] = newDp;
                    pd[i] = newPd;
                }
            }

            if (dp[i] == n) {
                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