| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 534515 | nicolexxuu | 은행 (IZhO14_bank) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
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[1000001];
for(int i = 0; i <= 1000000; 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");
}
}