#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;
const int N = 20;
const int M = 14;
const int masks = 1 << M;
bool dp[masks][N];
int main() {
int n, m;
cin >> n >> m;
vector<int>a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int>b(m);
for (int i = 0; i < m; i++) {
cin >> b[i];
}
if (n == 1) {
for (int mask = 0; mask < (1 << m); mask++) {
int cur = 0;
for (int j = 0; j < m; j++) {
if (mask & (1 << j)) {
cur += b[j];
}
}
if (cur == a[0]) {
cout << "YES";
return 0;
}
}
cout << "NO";
return 0;
}
if (n <= 20 && m <= 14) {
memset(dp, 0, sizeof(dp));
dp[0][0] = true;
for (int mask = 0; mask < (1 << m); mask++) {
for (int j = 0; j < n; j++) {
if (!dp[mask][j])continue;
int lost = (~mask + (1<<m)) % (1 << m);
for (int submask = lost;; submask = (submask - 1) & lost) {
int sum = 0;
for (int t = 0; t < m; t++) {
if (submask & (1 << t)) {
sum += b[t];
}
}
if (sum == a[j]) {
dp[mask + submask][j + 1] = true;
}
if (submask == 0)break;
}
}
}
for (int mask = 0; mask < (1 << m); mask++) {
if (dp[mask][n]) {
cout << "YES";
return 0;
}
}
cout << "NO";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
72 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
71 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
632 KB |
Output is correct |
2 |
Correct |
2 ms |
632 KB |
Output is correct |
3 |
Correct |
2 ms |
632 KB |
Output is correct |
4 |
Correct |
2 ms |
632 KB |
Output is correct |
5 |
Correct |
2 ms |
632 KB |
Output is correct |
6 |
Correct |
2 ms |
632 KB |
Output is correct |
7 |
Correct |
2 ms |
632 KB |
Output is correct |
8 |
Correct |
2 ms |
632 KB |
Output is correct |
9 |
Correct |
2 ms |
632 KB |
Output is correct |
10 |
Correct |
2 ms |
632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
632 KB |
Output is correct |
2 |
Correct |
3 ms |
632 KB |
Output is correct |
3 |
Correct |
4 ms |
632 KB |
Output is correct |
4 |
Correct |
3 ms |
632 KB |
Output is correct |
5 |
Correct |
4 ms |
632 KB |
Output is correct |
6 |
Correct |
3 ms |
632 KB |
Output is correct |
7 |
Correct |
4 ms |
632 KB |
Output is correct |
8 |
Correct |
4 ms |
632 KB |
Output is correct |
9 |
Correct |
4 ms |
632 KB |
Output is correct |
10 |
Correct |
4 ms |
632 KB |
Output is correct |
11 |
Correct |
3 ms |
632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
72 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
71 ms |
256 KB |
Output is correct |
10 |
Correct |
3 ms |
632 KB |
Output is correct |
11 |
Correct |
2 ms |
632 KB |
Output is correct |
12 |
Correct |
2 ms |
632 KB |
Output is correct |
13 |
Correct |
2 ms |
632 KB |
Output is correct |
14 |
Correct |
2 ms |
632 KB |
Output is correct |
15 |
Correct |
2 ms |
632 KB |
Output is correct |
16 |
Correct |
2 ms |
632 KB |
Output is correct |
17 |
Correct |
2 ms |
632 KB |
Output is correct |
18 |
Correct |
2 ms |
632 KB |
Output is correct |
19 |
Correct |
2 ms |
632 KB |
Output is correct |
20 |
Correct |
4 ms |
632 KB |
Output is correct |
21 |
Correct |
3 ms |
632 KB |
Output is correct |
22 |
Correct |
4 ms |
632 KB |
Output is correct |
23 |
Correct |
3 ms |
632 KB |
Output is correct |
24 |
Correct |
4 ms |
632 KB |
Output is correct |
25 |
Correct |
3 ms |
632 KB |
Output is correct |
26 |
Correct |
4 ms |
632 KB |
Output is correct |
27 |
Correct |
4 ms |
632 KB |
Output is correct |
28 |
Correct |
4 ms |
632 KB |
Output is correct |
29 |
Correct |
4 ms |
632 KB |
Output is correct |
30 |
Correct |
3 ms |
632 KB |
Output is correct |
31 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
32 |
Halted |
0 ms |
0 KB |
- |