oj.uz

Submission #404137

# Submission time Handle Problem Language Result Execution time Memory
404137 2021-05-13T21:02:16 Z fadi57 Bank (IZhO14_bank) C++14
100 / 100
 680 ms 94380 KB 
#include<bits/stdc++.h>
using namespace std;
const int mx=30;
typedef long long ll;
int inf=1e9+10;
const int mod=1e9+7;
int a[30];
int b[30];
int x[mx];
int n,m;
vector<int>sums[20005];
map<int,int>mp;
int dp[21][(1<<20)+2];
int solve(int i,int mask){

if(i==n){


        return 1;

}
int &ret=dp[i][mask];
  if(ret!=-1){

    return ret;
   }
ret=0;
for(auto it:sums[a[i]]){

    if((it&mask)==it){
        ret=max(solve(i+1,mask^it),ret);
    }
}
return ret;

}


int main(){

cin>>n>>m;

for(int i=0;i<n;i++){
    cin>>a[i];

}
for(int i=0;i<m;i++){
    cin>>b[i];


}
for(int i=0;i<(1<<m);i++){
   int sum=0;
   for(int j=0;j<m;j++){
    if(i&(1<<j)){
        sum+=b[j];
    }
   }
   sums[sum].push_back(i);

 }
 memset(dp,-1,sizeof(dp));
// cout<<sums[3][0];

if(solve(0,(1<<m)-1)){

cout<<"YES";
   }else{
   cout<<"NO";

   }





 }

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 86900 KB Output is correct
2 Correct 41 ms 86900 KB Output is correct
3 Correct 40 ms 86932 KB Output is correct
4 Correct 43 ms 87156 KB Output is correct
5 Correct 129 ms 93232 KB Output is correct
6 Correct 40 ms 86932 KB Output is correct
7 Correct 40 ms 86976 KB Output is correct
8 Correct 113 ms 92356 KB Output is correct
9 Correct 111 ms 92772 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 86948 KB Output is correct
2 Correct 41 ms 86896 KB Output is correct
3 Correct 47 ms 86968 KB Output is correct
4 Correct 40 ms 86844 KB Output is correct
5 Correct 40 ms 86912 KB Output is correct
6 Correct 45 ms 86852 KB Output is correct
7 Correct 43 ms 86864 KB Output is correct
8 Correct 46 ms 86828 KB Output is correct
9 Correct 42 ms 86896 KB Output is correct
10 Correct 42 ms 86924 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 87116 KB Output is correct
2 Correct 42 ms 86988 KB Output is correct
3 Correct 44 ms 87108 KB Output is correct
4 Correct 41 ms 86988 KB Output is correct
5 Correct 41 ms 87000 KB Output is correct
6 Correct 42 ms 87012 KB Output is correct
7 Correct 42 ms 87068 KB Output is correct
8 Correct 43 ms 87076 KB Output is correct
9 Correct 43 ms 86996 KB Output is correct
10 Correct 42 ms 87040 KB Output is correct
11 Correct 41 ms 86916 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 86900 KB Output is correct
2 Correct 41 ms 86900 KB Output is correct
3 Correct 40 ms 86932 KB Output is correct
4 Correct 43 ms 87156 KB Output is correct
5 Correct 129 ms 93232 KB Output is correct
6 Correct 40 ms 86932 KB Output is correct
7 Correct 40 ms 86976 KB Output is correct
8 Correct 113 ms 92356 KB Output is correct
9 Correct 111 ms 92772 KB Output is correct
10 Correct 40 ms 86948 KB Output is correct
11 Correct 41 ms 86896 KB Output is correct
12 Correct 47 ms 86968 KB Output is correct
13 Correct 40 ms 86844 KB Output is correct
14 Correct 40 ms 86912 KB Output is correct
15 Correct 45 ms 86852 KB Output is correct
16 Correct 43 ms 86864 KB Output is correct
17 Correct 46 ms 86828 KB Output is correct
18 Correct 42 ms 86896 KB Output is correct
19 Correct 42 ms 86924 KB Output is correct
20 Correct 42 ms 87116 KB Output is correct
21 Correct 42 ms 86988 KB Output is correct
22 Correct 44 ms 87108 KB Output is correct
23 Correct 41 ms 86988 KB Output is correct
24 Correct 41 ms 87000 KB Output is correct
25 Correct 42 ms 87012 KB Output is correct
26 Correct 42 ms 87068 KB Output is correct
27 Correct 43 ms 87076 KB Output is correct
28 Correct 43 ms 86996 KB Output is correct
29 Correct 42 ms 87040 KB Output is correct
30 Correct 41 ms 86916 KB Output is correct
31 Correct 116 ms 93460 KB Output is correct
32 Correct 179 ms 92628 KB Output is correct
33 Correct 117 ms 93128 KB Output is correct
34 Correct 121 ms 93512 KB Output is correct
35 Correct 139 ms 94380 KB Output is correct
36 Correct 123 ms 93924 KB Output is correct
37 Correct 118 ms 94208 KB Output is correct
38 Correct 118 ms 93992 KB Output is correct
39 Correct 138 ms 91800 KB Output is correct
40 Correct 124 ms 93844 KB Output is correct
41 Correct 119 ms 93300 KB Output is correct
42 Correct 118 ms 92416 KB Output is correct
43 Correct 118 ms 94080 KB Output is correct
44 Correct 145 ms 94268 KB Output is correct
45 Correct 116 ms 93120 KB Output is correct
46 Correct 117 ms 94228 KB Output is correct
47 Correct 120 ms 93676 KB Output is correct
48 Correct 111 ms 92616 KB Output is correct
49 Correct 112 ms 92868 KB Output is correct
50 Correct 346 ms 91924 KB Output is correct
51 Correct 129 ms 92740 KB Output is correct
52 Correct 118 ms 91700 KB Output is correct
53 Correct 680 ms 91788 KB Output is correct
54 Correct 417 ms 91920 KB Output is correct
55 Correct 334 ms 91928 KB Output is correct
56 Correct 354 ms 91936 KB Output is correct
57 Correct 390 ms 92008 KB Output is correct
58 Correct 362 ms 91916 KB Output is correct