| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1001414 | vjudge1 | Bank (IZhO14_bank) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define pll pair<long long, long long>
#define pii pair<int , int>
#define fi first
#define se second
#define x first
#define y second
#define bit(i,j) ((j >> i) & 1)
using namespace std;
const long long inf = 1e9+1;
const int mod = 1e9+7;
const int MAXN = 2e5+100;
bool dp[25][(1<<20)+1];
int cnt[(1 << 20) + 1];
int32_t main(){
//freopen("A.inp", "r", stdin);
//freopen("A.out", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
int n , m; cin >> n >> m;
vector<int> pre(n+1) , a(n+1) , b(m+1);
for(int i = 1; i <= n ; i ++) cin >> a[i] , pre[i] = pre[i-1] + a[i];
for(int i = 1; i <= m ; i ++) cin >> b[i];
for(int msk = 1 ; msk < (1 << m) ; msk++){
for(int i = 0 ; i < m ; i++) if(bit(i , msk)) cnt[msk] += b[i+1];
}
dp[0][0] = 1;
for(int i = 1 ; i <= n ; i++){
for(int msk = 1 ; msk < (1 << m) ; msk++){
if(cnt[msk] != pre[i]) continue;
for(int s = msk ; s > 0 ; s = (s-1) & msk){
if(cnt[s] == a[i]) dp[i][msk] = max(dp[i][msk] , dp[i-1][msk ^ s]);
}
}
}
int res = 0;
for(int msk = 1 ; msk < (1 << m) ; msk++){
res = max(res , dp[n][msk]);
}
cout << (res ? "YES\n" : "NO\n");
return 0;
}