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 F first
#define S second
#define SZ(x) int((x).size())
const char nl = '\n';
using namespace std;
int sum[(1 << 20)];
vector<int> v[1010];
int a[20], b[20];
int n, m;
bool dp[20][(1 << 20)];
// dp[i][mask] = true, if [0; i] can be payed with #mask of B
void verkefni() {
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 ++) {
for (int i = 0; i < m; i ++) {
if (mask & (1 << i)) sum[mask] += b[i];
}
}
for (int i = 0; i < n; i ++) {
for (int mask = 0; mask < (1 << m); mask ++) {
if (sum[mask] == a[i]) {
v[a[i]].push_back(mask);
}
}
}
for (auto el : v[a[0]]) {
dp[0][el] = true;
}
for (int mask = 0; mask < (1 << m); mask ++) {
if (dp[0][mask]) {
for (int i = 0; i < m; i ++) {
if (mask != (mask | (1 << i))) {
// cout << mask << " " << (mask | (1 << i)) << nl;
}
dp[0][mask | (1 << i)] = true;
}
}
}
int tot = 0;
for (int i = 0; i < n; i ++) {
for (int mask = 0; mask < (1 << m); mask ++) {
if (i > 0) {
if (!dp[i-1][mask]) continue;
} else {
if (!dp[i][mask]) continue;
}
if (sum[mask] - tot == a[i]) {
dp[i][mask] = true;
for (int j = 0; j < m; j ++) {
dp[i][mask | (1 << j)] = true;
}
}
}
tot += a[i];
}
// cout << "\n-----------------\n";
if (dp[n-1][(1 << m)-1]) {
cout << "YES";
} else {
cout << "NO";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tst = 1;
// cin >> tst;
while (tst --) {
verkefni();
cout << nl;
}
}
# | 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... |