#include<bits/stdc++.h>
using namespace std;
bool dp[(1 << 20)+1][21];
long long res[(1 << 21)];
bool ok = false;
long dept[50], money[50], pre[50], n, m;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for(long i = 1; i <= n; i++){
cin >> dept[i];
pre[i] = pre[i-1] + dept[i];
}
for(long i = 0; i < m; i++) cin >> money[i];
for(long i = 0; i < (1 << m); i++){
dp[i][0] = true;
for(long p = 0; p < m; p++){
if(i & (1 << p)){
res[i] = res[i] + money[p];
}
}
}
for(long i = 1; i <= n; i++){
for(long j = 0; j < (1 << m); j++){
for(long p = 0; p < m; p++){
if(!(j & (1 << p))){
long u = j | (1 << p);
if(dp[j][i] == true){
dp[u][i] = true;
if(i == n) ok = true;
}
if(dp[j][i-1] == true){
if(res[u] - pre[i-1] == dept[i]){
dp[u][i] = true;
if(i == n) ok = true;
}
}
}
}
}
}
if(ok == true) cout << "YES";
else cout << "NO";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2408 KB |
Output is correct |
4 |
Correct |
5 ms |
6748 KB |
Output is correct |
5 |
Correct |
143 ms |
32084 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
143 ms |
32144 KB |
Output is correct |
9 |
Correct |
143 ms |
32336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2520 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2392 KB |
Output is correct |
5 |
Correct |
1 ms |
2392 KB |
Output is correct |
6 |
Correct |
1 ms |
2520 KB |
Output is correct |
7 |
Correct |
1 ms |
2392 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4444 KB |
Output is correct |
2 |
Correct |
4 ms |
4700 KB |
Output is correct |
3 |
Correct |
11 ms |
4700 KB |
Output is correct |
4 |
Correct |
15 ms |
4700 KB |
Output is correct |
5 |
Correct |
11 ms |
4700 KB |
Output is correct |
6 |
Correct |
7 ms |
4444 KB |
Output is correct |
7 |
Correct |
5 ms |
4444 KB |
Output is correct |
8 |
Correct |
5 ms |
4444 KB |
Output is correct |
9 |
Correct |
9 ms |
4700 KB |
Output is correct |
10 |
Correct |
9 ms |
4568 KB |
Output is correct |
11 |
Correct |
15 ms |
4700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2408 KB |
Output is correct |
4 |
Correct |
5 ms |
6748 KB |
Output is correct |
5 |
Correct |
143 ms |
32084 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
143 ms |
32144 KB |
Output is correct |
9 |
Correct |
143 ms |
32336 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
2520 KB |
Output is correct |
12 |
Correct |
1 ms |
2396 KB |
Output is correct |
13 |
Correct |
1 ms |
2392 KB |
Output is correct |
14 |
Correct |
1 ms |
2392 KB |
Output is correct |
15 |
Correct |
1 ms |
2520 KB |
Output is correct |
16 |
Correct |
1 ms |
2392 KB |
Output is correct |
17 |
Correct |
1 ms |
2396 KB |
Output is correct |
18 |
Correct |
1 ms |
2396 KB |
Output is correct |
19 |
Correct |
1 ms |
2396 KB |
Output is correct |
20 |
Correct |
8 ms |
4444 KB |
Output is correct |
21 |
Correct |
4 ms |
4700 KB |
Output is correct |
22 |
Correct |
11 ms |
4700 KB |
Output is correct |
23 |
Correct |
15 ms |
4700 KB |
Output is correct |
24 |
Correct |
11 ms |
4700 KB |
Output is correct |
25 |
Correct |
7 ms |
4444 KB |
Output is correct |
26 |
Correct |
5 ms |
4444 KB |
Output is correct |
27 |
Correct |
5 ms |
4444 KB |
Output is correct |
28 |
Correct |
9 ms |
4700 KB |
Output is correct |
29 |
Correct |
9 ms |
4568 KB |
Output is correct |
30 |
Correct |
15 ms |
4700 KB |
Output is correct |
31 |
Correct |
217 ms |
32084 KB |
Output is correct |
32 |
Correct |
294 ms |
32340 KB |
Output is correct |
33 |
Correct |
602 ms |
32156 KB |
Output is correct |
34 |
Correct |
831 ms |
32360 KB |
Output is correct |
35 |
Correct |
906 ms |
32340 KB |
Output is correct |
36 |
Execution timed out |
1008 ms |
32360 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |