| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 810882 | 2023-08-06T17:07:42 Z | Username_taken12 | Bank (IZhO14_bank) | C++17 | 0 ms | 0 KB |
// Source: https://usaco.guide/general/io
import java.io.*;
import java.util.*;
import java.lang.Integer;
public class Bank {
public static void main(String[] args) throws IOException {
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);
StringTokenizer st = new StringTokenizer(r.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] ppl = new int[N+1];
ppl[N]=0;
int[] mon = new int[M];
st= new StringTokenizer(r.readLine());
for(int i = 0; i<N; i++)
ppl[i]=Integer.parseInt(st.nextToken());
st= new StringTokenizer(r.readLine());
for(int j=0; j<M; j++)
mon[j]=Integer.parseInt(st.nextToken());
int[][] dp = new int[(1<<M)][2]; //ppl remaining
for(int i=0; i<(1<<M); i++)
dp[i]=new int[]{-1, Integer.MAX_VALUE};
dp[0]=new int[]{0, ppl[0]};
boolean pos=false;
for(int i=0; i<M+1; i++){
for(int j = 0; j<(1<<M); j++)
{
if(Integer.bitCount(j)!=i)
continue;
//System.out.println(Integer.toBinaryString(j));
//System.out.println(Arrays.toString(dp[j]));
if(dp[j][0]==N){
pos=true;
break;
}
if(dp[j][0]==-1)
continue;
for(int k=0; k<M; k++)
{
//System.out.print(k);
if((j&(1<<k))!=0){
//System.out.println(" continue!");
continue;
}
//System.out.println();
if(dp[j][1]==mon[k]){
dp[j+(1<<k)]=new int[]{dp[j][0]+1, ppl[dp[j][0]+1]};
//if(dp[j][0]+1==N)
// System.out.println(j+(1<<k)+" "+Arrays.toString(dp[j+(1<<k)]));
}
if(dp[j][1]>mon[k])
dp[j+(1<<k)]=new int[]{dp[j][0], dp[j][1]-mon[k]};
}
}
//System.out.println();
if(pos)
break;
}
//for(int i=0; i)
if(pos)
pw.println("YES");
else
pw.println("NO");
pw.close();
}
}