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>
using namespace std;
const int N = 1200000;
int n, m, a[30], b[30], sum_a[30], sum_b[N];
bool dp[N][30];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
sum_a[i] = a[i] + sum_a[i - 1];
}
for (int i = 1; i <= m; i ++) {
cin >> b[i];
//cout << i << " : " << b[i] << "\n";
}
if (n > m) {
cout << "NO";
return 0;
}
int k = 1 << m;
for (int i = 1; i < k; i ++) {
for (int j = 0; j < m; j ++) {
if ((i >> j) & 1) {
sum_b[i] = sum_b[i - (1 << j)] + b[j + 1];
//cout << i << " , " << j << " " << b[j + 1] << " " << sum_b[i] << "\n";
break;
}
}
}
dp[0][0] = true;
for (int i = 0; i <= n; i ++) {
for (int j = 0; j < k; j ++) {
if (dp[i][j]) {
if (sum_a[i] == sum_b[j]) {
dp[i + 1][j] = true;
//cout << "check " << i << " , " << j << "\n";
}
if (sum_a[i] > sum_b[j]) {
for (int t = 0; t < m; t ++) {
if (((j >> t) & 1) == 0) {
if (sum_a[i] >= sum_b[j + (1 << t)]) {
dp[i][j + (1 << t)] = true;
}
//cout << "new " << i << " , " << j << " , " << t << "\n";
}
}
}
}
}
}
bool yes = false;
for (int i = 1; i < k; i ++) {
if ((sum_a[n] == sum_b[i]) && dp[n][i]) {
yes = true;
//cout << i << " : " << sum_a[n] << " , " << sum_b[i] << "\n";
break;
}
}
if (yes) {
cout << "YES";
} else {
cout << "NO";
}
return 0;
}
# | 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... |