# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
712561 |
2023-03-19T07:16:04 Z |
nishantc1527 |
Bank (IZhO14_bank) |
C++14 |
|
1000 ms |
6904 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifdef debug
#include "debug.h"
#endif
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
const int mod = (int) 1e9 + 7;
const int inf = 1061109567;
const ll infll = 4557430888798830399;
const int MAX_N = 20;
int n, m;
int a[MAX_N];
int b[MAX_N];
int dp[MAX_N][1 << MAX_N];
int sum[1 << MAX_N];
void solve() {
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 curr = 0;
for(int i = 0; i < m; i ++) if((mask >> i) & 1) curr += b[i];
sum[mask] = curr;
}
if(n == 1) {
int ans = 0;
for(int mask = 0; mask < 1 << m; mask ++) if(sum[mask] == a[0]) ans = 1;
if(ans) cout << "YES\n";
else cout << "NO\n";
return;
}
for(int i = 0; i < n; i ++) {
for(int mask = 0; mask < 1 << m; mask ++) {
for(int sub = mask; sub; sub = (sub - 1) & mask) {
if(sum[sub] == a[i]) {
if(i == 0) dp[i][mask] = 1;
else dp[i][mask] |= dp[i - 1][mask ^ sub];
}
}
}
}
int ans = 0;
for(int mask = 0; mask < 1 << m; mask ++) ans |= dp[n - 1][mask];
if(ans) cout << "YES\n";
else cout << "NO\n";
}
int main() {
#ifndef debug
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
#ifdef debug
int i = 1;
t = 1e5;
#endif
while(t --) {
#ifdef debug
cout << "Case #" << i ++ << ": ";
#endif
solve();
cout << flush;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
56 ms |
4396 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
58 ms |
4332 KB |
Output is correct |
9 |
Correct |
57 ms |
4300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
724 KB |
Output is correct |
2 |
Correct |
11 ms |
584 KB |
Output is correct |
3 |
Correct |
36 ms |
956 KB |
Output is correct |
4 |
Correct |
50 ms |
1100 KB |
Output is correct |
5 |
Correct |
37 ms |
884 KB |
Output is correct |
6 |
Correct |
19 ms |
460 KB |
Output is correct |
7 |
Correct |
16 ms |
596 KB |
Output is correct |
8 |
Correct |
12 ms |
572 KB |
Output is correct |
9 |
Correct |
30 ms |
832 KB |
Output is correct |
10 |
Correct |
29 ms |
800 KB |
Output is correct |
11 |
Correct |
49 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
56 ms |
4396 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
58 ms |
4332 KB |
Output is correct |
9 |
Correct |
57 ms |
4300 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
26 ms |
724 KB |
Output is correct |
21 |
Correct |
11 ms |
584 KB |
Output is correct |
22 |
Correct |
36 ms |
956 KB |
Output is correct |
23 |
Correct |
50 ms |
1100 KB |
Output is correct |
24 |
Correct |
37 ms |
884 KB |
Output is correct |
25 |
Correct |
19 ms |
460 KB |
Output is correct |
26 |
Correct |
16 ms |
596 KB |
Output is correct |
27 |
Correct |
12 ms |
572 KB |
Output is correct |
28 |
Correct |
30 ms |
832 KB |
Output is correct |
29 |
Correct |
29 ms |
800 KB |
Output is correct |
30 |
Correct |
49 ms |
340 KB |
Output is correct |
31 |
Execution timed out |
1064 ms |
6904 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |