Submission #278807

#	Time	Username	Problem	Language	Result	Execution time	Memory
278807		KWang31	Bank (IZhO14_bank)	Java	100 / 100	847 ms	98160 KiB

bank

import java.io.*; import java.util.*;
public class bank {
    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;
                int val=val(mask|(1<<k));
                if(val==pref[i]){
                    
                    dp[i][mask|(1<<k)]=true;
                    arl[i].add(mask|(1<<k));
                }else if(val<pref[i]){
                    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;
    }
}

Compilation message (stderr)

Note: bank.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

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