제출 #1349851

#제출 시각아이디문제언어결과실행 시간메모리
1349851sameerBank (IZhO14_bank)C++20
100 / 100
425 ms181180 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
ll i, j, t, k, n, m, a[21], b[21], su[(1 << 21)], po[21][(1 << 21)];

void run(){
 cin >> n >> m;
 for( i = 1; i <= n; i++) cin >> a[i], a[i] += a[i-1];
 for( i = 0; i < m; i++) cin >> b[i];
 su[0] = 0; po[0][0] = 1;
 for( i = 1; i < (1 << m); i++) su[i] = b[__builtin_ffs(i)-1]+su[i & (i-1)], po[0][i] = 1;

 for( i = 1; i <= n; i++){
 for( j = 1; j < (1 << m); j++){
 if(su[j] == a[i] && po[i-1][j] == 1){
 po[i][j] = 1; continue;
 }
 t = j;
 while(t){
 po[i][j] |= po[i][j-(1 << (__builtin_ffs(t)-1))];
 t = t & t-1;
 }
 // for( k = 0; k < m; k++) if((j >> k) & 1) po[i][j] |= po[i][j-(1 << k)];
 }
 }
 for( i = 1; i < (1 << m); i++) if(po[n][i]) 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--)
 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...