Submission #1349524

#TimeUsernameProblemLanguageResultExecution timeMemory
1349524sameerBank (IZhO14_bank)C++20
71 / 100
1095 ms1468 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
ll i, n, m, va[21], a[21], b[21]; bool po[100][(1 << 15)];

void divi(int v, int l, int r){
 int i, j, k, t;
 if(l == r){
 for( i = 0; i < (1 << m); i++){
 t = 0;
 for( k = 0; k < m; k++) if((i >> k) & 1) t += b[k];
 if(t == a[l]) po[v][i] = 1;
 }
 return;
 } int mm = (l+r)/2;
 divi(v*2, l, mm); divi(v*2+1, mm+1, r);
 for( i = 1; i < (1 << m); i++){
 if(po[v*2][i] == 0) continue;
 j = 0; k = 0;
 while(k < m){
 if((i >> k) % 2 == 0) va[j] = (1 << k), j++;
 k++;
 }
 for( j = 1; j < (1 << (m-__builtin_popcount(i))); j++){
 t = 0;
 for( k = 0; k < (m-__builtin_popcount(i)); k++) if((j >> k) & 1) t += va[k];
 if(po[v*2+1][t]) po[v][i+t] = 1;
 }
 }
}

void run(){
 cin >> n >> m;
 for( i = 0; i < n; i++) cin >> a[i];
 for( i = 0; i < m; i++) cin >> b[i];
 if(n > m){
 cout << "NO\n"; return;
 }
 divi(1, 0, n-1);
 for( i = 0; i < (1 << m); i++) if(po[1][i] == 1) break;
 (i < (1 << m))? cout << "YES\n": cout << "NO\n";
}

int main(){
 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 // int tt; cin >> tt; while(tt--)
 // cout << __builtin_ffs(8)-1 << ' ';
 run();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...