Submission #534517

#	Time	Username	Problem	Language	Result	Execution time	Memory
534517		nicolexxuu	Bank (IZhO14_bank)	Java	52 / 100	1087 ms	46660 KiB

bank

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

public class bank {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int[] a = new int[N], b = new int[M];
		for(int i = 0; i < N; i++) a[i] = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < M; i++) b[i] = Integer.parseInt(st.nextToken());
		br.close();
		
		ArrayList<Integer> combos[] = new ArrayList[20001];
		for(int i = 0; i <= 20000; i++) combos[i] = new ArrayList<>();
		combos[0].add(0);
		for(int mask = 1; mask < 1 << M; mask++) {
			int sum = 0;
			for(int i = 0; i < M; i++) {
//				System.out.println(mask & (1 << i));
				if((mask & (1 << i)) > 0) sum += b[i];
			}
//			System.out.println("mask: " + mask + " sum: " + sum);
			combos[sum].add(mask);
		}
		
//		for(int s = 0; s <= 1000; s++) System.out.println(combos[s]);
		boolean[][] possible = new boolean[N+1][1 << M];
		possible[0][0] = true;
		for(int i = 0; i < N; i++) {
//			System.out.println("i: " + i);
			for(int mask = 1; mask < 1 << M; mask++) {
//				System.out.println("mask: " + Integer.toBinaryString(mask));
				for(int combo : combos[a[i]]) {
//					if(mask == 31) System.out.println("combo: " + Integer.toBinaryString(combo));
					boolean ok = true;
					for(int j = 0; j < M; j++) {
//						System.out.println(Integer.toBinaryString(((combo >> j) & 1)) + " vs " + Integer.toBinaryString(((mask >> j) & 1)));
						if(((combo >> j) & 1) == 1 &&  ((mask >> j) & 1) == 0) ok = false;
					}
//					if(mask == 31) System.out.println("ok: " + ok);
					if(ok) possible[i+1][mask] |= possible[i][mask - combo];
				}
//				System.out.println(possible[i+1][mask]);
			}
		}
		
		boolean result = false;
		for(int i = 0; i < 1 << M; i++) result |= possible[N][i];
		if(result) System.out.println("YES");
		else System.out.println("NO");
	}
}

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