| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 278799 | KWang31 | 은행 (IZhO14_bank) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.io.*; import java.util.*;
public class P2 {
static class FastReader
{
BufferedReader br;
StringTokenizer st;
public FastReader()
{
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt()
{
return Integer.parseInt(next());
}
}
static boolean[] visited;
static int[] pref;
static int[]b;
static int M;
static boolean[][] dp;
static ArrayList<Integer> arl[];
//SOS DP (SEE ANALYSIS)
public static void main(String[] args) {
FastReader br=new FastReader();
int N=br.nextInt();
M=br.nextInt();
int[] a=new int[N];
for (int i = 0; i < N; i++) {
a[i]=br.nextInt();
}
b=new int[M];
for (int i = 0; i < M; i++) {
b[i]=br.nextInt();
}
dp=new boolean[N+1][1<<M];
dp[0][0]=true;
pref=new int[N+1];
for (int i = 1; i <=N; i++) {
pref[i]=pref[i-1]+a[i-1];
}
arl=new ArrayList[N+1];
for (int i = 0; i <=N; i++) {
arl[i]=new ArrayList<>();
}
arl[0].add(0);
for (int j = 1; j <=N; j++) {
//Look at arl[j-1]
visited=new boolean[1<<M];
for (int i : arl[j-1]) {
visited[i]=true;
dfs(i,M-1,j);
}
}
if(!arl[N].isEmpty()){
System.out.println("YES"); return;
}
System.out.println("NO");
}
public static void dfs(int mask, int k, int i){
//Finding all supermasks that differ than mask in the last k bits
if(k>=0){
dfs(mask,k-1,i);
if((mask&(1<<k))==0 && !visited[mask|(1<<k)]){//If already visited, I don't need to visit
visited[mask|(1<<k)]=true;
if(val(mask|(1<<k))==pref[i]){
dp[i][mask|(1<<k)]=true;
arl[i].add(mask|(1<<k));
}
dfs((mask|(1<<k)),k-1,i);
}
}
}
public static int val(int mask){
int a=0;
for (int i = 0; i < M; i++) {
if((mask&(1<<i))>0){
a+=b[i];
}
}
return a;
}
}