# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
90519 | 2018-12-22T05:47:45 Z | daniel_02 | Bank (IZhO14_bank) | C++14 | 66 ms | 1644 KB |
#include <bits/stdc++.h> #define fr first #define pb push_back #define sc second #define ll long long using namespace std; const int N = 23; int a[N], b[N]; bool dp[N][(1 << 20) + 7]; vector<int>v; main() { int n, m, x; cin >> n >> m; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for (int i = 1; i <= m; i++) { scanf("%d", &b[i]); } for (int msk = 1; msk < (1 << m); msk++) { int sm = 0; for (int i = 0; i < m; i++) { if (msk & (1 << i)) { sm += b[i + 1]; } } if (sm == a[1]) { //cout << 1 << " " << msk << endl; dp[1][msk] = 1; } } for (int i = 2; i <= n; i++) { for (int msk = 1; msk < (1 << m); msk++) { if (!dp[i - 1][msk])continue; for (int j = 0; j < m; j++) { if (!(msk & (1 << j))) { v.pb(j + 1); } } int sz = v.size(); for (int msk1 = 1; msk1 < (1 << sz); msk1++) { int sm = 0; for (int j = 0; j < sz; j++) { if (msk1 & (1 << j)) { sm += b[v[j]]; } } if (sm == a[i]) { int tmp = msk; for (int j = 0; j < sz; j++) { if (msk1 & (1 << j)) { tmp = (tmp | (v[j] - 1)); //cout << j << " " << v[j] << endl; } } //cout << i << " " << msk << " " << tmp << endl; dp[i][tmp] = 1; } } v.clear(); } } for (int msk = 1; msk < (1 << m); msk++) { if (dp[n][msk]) { puts("YES"); return 0; } } puts("NO"); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 468 KB | Output is correct |
3 | Correct | 2 ms | 524 KB | Output is correct |
4 | Correct | 3 ms | 524 KB | Output is correct |
5 | Correct | 66 ms | 524 KB | Output is correct |
6 | Correct | 2 ms | 532 KB | Output is correct |
7 | Correct | 2 ms | 544 KB | Output is correct |
8 | Correct | 66 ms | 1644 KB | Output is correct |
9 | Correct | 66 ms | 1644 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 1644 KB | Output is correct |
2 | Incorrect | 2 ms | 1644 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 1644 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 468 KB | Output is correct |
3 | Correct | 2 ms | 524 KB | Output is correct |
4 | Correct | 3 ms | 524 KB | Output is correct |
5 | Correct | 66 ms | 524 KB | Output is correct |
6 | Correct | 2 ms | 532 KB | Output is correct |
7 | Correct | 2 ms | 544 KB | Output is correct |
8 | Correct | 66 ms | 1644 KB | Output is correct |
9 | Correct | 66 ms | 1644 KB | Output is correct |
10 | Correct | 2 ms | 1644 KB | Output is correct |
11 | Incorrect | 2 ms | 1644 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |