oj.uz

Submission #278807

# Submission time Handle Problem Language Result Execution time Memory
278807 2020-08-21T23:20:15 Z KWang31 Bank (IZhO14_bank) Java 11
100 / 100
 847 ms 98160 KB 
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

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

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 10212 KB Output is correct
2 Correct 79 ms 10232 KB Output is correct
3 Correct 76 ms 10360 KB Output is correct
4 Correct 87 ms 11128 KB Output is correct
5 Correct 79 ms 13304 KB Output is correct
6 Correct 75 ms 10088 KB Output is correct
7 Correct 77 ms 10416 KB Output is correct
8 Correct 172 ms 15544 KB Output is correct
9 Correct 184 ms 15132 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 10216 KB Output is correct
2 Correct 85 ms 10264 KB Output is correct
3 Correct 82 ms 10344 KB Output is correct
4 Correct 75 ms 10344 KB Output is correct
5 Correct 76 ms 10372 KB Output is correct
6 Correct 76 ms 10296 KB Output is correct
7 Correct 77 ms 10472 KB Output is correct
8 Correct 81 ms 10232 KB Output is correct
9 Correct 79 ms 10216 KB Output is correct
10 Correct 79 ms 10488 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 10616 KB Output is correct
2 Correct 81 ms 10744 KB Output is correct
3 Correct 79 ms 10600 KB Output is correct
4 Correct 78 ms 10744 KB Output is correct
5 Correct 79 ms 10700 KB Output is correct
6 Correct 78 ms 10472 KB Output is correct
7 Correct 88 ms 11384 KB Output is correct
8 Correct 94 ms 11544 KB Output is correct
9 Correct 79 ms 10412 KB Output is correct
10 Correct 80 ms 10592 KB Output is correct
11 Correct 99 ms 11636 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 10212 KB Output is correct
2 Correct 79 ms 10232 KB Output is correct
3 Correct 76 ms 10360 KB Output is correct
4 Correct 87 ms 11128 KB Output is correct
5 Correct 79 ms 13304 KB Output is correct
6 Correct 75 ms 10088 KB Output is correct
7 Correct 77 ms 10416 KB Output is correct
8 Correct 172 ms 15544 KB Output is correct
9 Correct 184 ms 15132 KB Output is correct
10 Correct 78 ms 10216 KB Output is correct
11 Correct 85 ms 10264 KB Output is correct
12 Correct 82 ms 10344 KB Output is correct
13 Correct 75 ms 10344 KB Output is correct
14 Correct 76 ms 10372 KB Output is correct
15 Correct 76 ms 10296 KB Output is correct
16 Correct 77 ms 10472 KB Output is correct
17 Correct 81 ms 10232 KB Output is correct
18 Correct 79 ms 10216 KB Output is correct
19 Correct 79 ms 10488 KB Output is correct
20 Correct 78 ms 10616 KB Output is correct
21 Correct 81 ms 10744 KB Output is correct
22 Correct 79 ms 10600 KB Output is correct
23 Correct 78 ms 10744 KB Output is correct
24 Correct 79 ms 10700 KB Output is correct
25 Correct 78 ms 10472 KB Output is correct
26 Correct 88 ms 11384 KB Output is correct
27 Correct 94 ms 11544 KB Output is correct
28 Correct 79 ms 10412 KB Output is correct
29 Correct 80 ms 10592 KB Output is correct
30 Correct 99 ms 11636 KB Output is correct
31 Correct 283 ms 18684 KB Output is correct
32 Correct 334 ms 21292 KB Output is correct
33 Correct 157 ms 27940 KB Output is correct
34 Correct 114 ms 32896 KB Output is correct
35 Correct 105 ms 34072 KB Output is correct
36 Correct 126 ms 65896 KB Output is correct
37 Correct 94 ms 15848 KB Output is correct
38 Correct 98 ms 19484 KB Output is correct
39 Correct 205 ms 37600 KB Output is correct
40 Correct 92 ms 31940 KB Output is correct
41 Correct 129 ms 65704 KB Output is correct
42 Correct 277 ms 24248 KB Output is correct
43 Correct 132 ms 29848 KB Output is correct
44 Correct 96 ms 42232 KB Output is correct
45 Correct 283 ms 20740 KB Output is correct
46 Correct 212 ms 26660 KB Output is correct
47 Correct 98 ms 42104 KB Output is correct
48 Correct 171 ms 16188 KB Output is correct
49 Correct 80 ms 13432 KB Output is correct
50 Correct 692 ms 92468 KB Output is correct
51 Correct 137 ms 33564 KB Output is correct
52 Correct 182 ms 34360 KB Output is correct
53 Correct 477 ms 42580 KB Output is correct
54 Correct 663 ms 89896 KB Output is correct
55 Correct 709 ms 92648 KB Output is correct
56 Correct 847 ms 98160 KB Output is correct
57 Correct 690 ms 95344 KB Output is correct
58 Correct 637 ms 92188 KB Output is correct