# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1222475 | lamlamlam | Bank (IZhO14_bank) | C++20 | 19 ms | 1348 KiB |
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define task "sus"
const int MN = 20;
int n,m,a[MN],b[MN];
bool dp[MN+1][(1<<MN)];
vector<int> v[MN][MN];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if(fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
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 mask=0; mask<(1<<m); mask++){
int sum = 0;
for(int i=0; i<m; i++) sum += (1 & (mask>>i)) * b[i];
for(int i=0; i<n; i++) if(sum==a[i]) {
int sus = __builtin_popcount(mask);
v[i][sus].push_back(mask);
}
}
dp[0][0] = true;
for(int i=0; i<n; i++){
for(int mask=0; mask<(1<<m); mask++){
int cnt = __builtin_popcount(mask);
if(cnt<i or cnt>n-i) continue;
for(int j=0; j<=i+m-n; j++){
for(auto x:v[i][j]){
if((x&mask) or !dp[i][mask]) continue;
dp[i+1][(x ^ mask)] = true;
}
}
}
}
bool sus = 0;
for(int mask=0; mask<(1<<m); mask++) if(dp[n][mask]) sus = true;
if(sus) cout << "YES";
else cout << "NO";
cerr << "\nTIME: " << clock() << '\n';
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |