Submission #630637

#	Time	Username	Problem	Language	Result	Execution time	Memory
630637		coderInTraining	Bank (IZhO14_bank)	Java	100 / 100	657 ms	20964 KiB

bank

import java.util.*;

public class bank {
    public static void main (String[]args) {
        Scanner scan = new Scanner (System.in);

        int peopleNumber = scan.nextInt();
        int bankNoteNumber = scan.nextInt();

        int [] salaries = new int [peopleNumber];

        for (int i = 0; i < peopleNumber; i++) {
            salaries[i] = scan.nextInt();
        }

        int [] bankNotes = new int [bankNoteNumber];

        for (int i = 0; i < bankNoteNumber; i++) {
            bankNotes[i] = scan.nextInt();
        }

        int subsetNumber = (int)Math.pow(2, bankNoteNumber);
        int [] maxPrefix = new int [subsetNumber];
        int [] leftOver = new int [subsetNumber];

        Arrays.fill(maxPrefix, Integer.MIN_VALUE);
        Arrays.fill(leftOver, Integer.MIN_VALUE);

        maxPrefix[0] = 0;
        leftOver[0] = 0;

        int max = 0;

        for (int i = 0; i < subsetNumber; i++) {

            int peopleFinished = maxPrefix[i];
            max = Math.max(max, peopleFinished);

            if (max == peopleNumber) {
                break;
            }

            if (peopleFinished == Integer.MIN_VALUE) {
                continue;
            }

            for (int j = 0; j < bankNoteNumber; j++) {
                // Checking if the current bank note has been unused
                if ((i & (1 << j)) == 0) {
                    int currentPersonTarget = salaries[peopleFinished];

                    int currentBankNote = bankNotes[j];
                    int currentLeftOver = leftOver[i];

                    int newIndex = i + (int)Math.pow(2, j);

                    if (currentLeftOver + currentBankNote < currentPersonTarget) {
                        maxPrefix[newIndex] = maxPrefix[i];
                        leftOver[newIndex] = currentLeftOver + currentBankNote;
                    }

                    if (currentLeftOver + currentBankNote == currentPersonTarget) {
                        maxPrefix[newIndex] = maxPrefix[i] + 1;
                        leftOver[newIndex] = 0;
                    }
                }
            }
        }

        if (max == peopleNumber) {
            System.out.println("YES");
        }
        else {
            System.out.println("NO");
        }
    }
}

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