# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
727431 | 2023-04-20T16:15:32 Z | josiftepe | Bank (IZhO14_bank) | C++14 | 252 ms | 113536 KB |
#include <iostream> #include <fstream> #include <vector> #include <map> #include <cstring> #include <queue> #include <algorithm> //#include <bits/stdc++.h> using namespace std; const int maxn = 1005 * 1005; vector<int> masks[maxn]; int salary[maxn]; int notes[maxn]; int dp[20][1 << 20]; int rec(int at, int bitmask) { if(at == -1) { return 1; } if(dp[at][bitmask] != -1) { return dp[at][bitmask]; } int result = 0; for(int i = 0; i < masks[salary[at]].size(); i++) { int tmp_mask = masks[salary[at]][i]; if((tmp_mask & bitmask) == tmp_mask) { result |= rec(at - 1, bitmask ^ tmp_mask); } } return dp[at][bitmask] = result; } int main() { ios::sync_with_stdio(0); int n, m; cin >> n >> m; for(int i = 0; i < n; i++) { cin >> salary[i]; } for(int i = 0; i < m; i++) { cin >> notes[i]; } for(int bitmask = 0; bitmask < (1 << m); bitmask++) { int sum = 0; for(int i = 0; i < m; i++) { if(bitmask & (1 << i)) { sum += notes[i]; } } masks[sum].push_back(bitmask); } memset(dp, -1, sizeof dp); cout << (rec(n - 1, (1 << m) - 1) == 1 ? "YES" : "NO") << endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 42 ms | 106072 KB | Output is correct |
2 | Correct | 45 ms | 106040 KB | Output is correct |
3 | Correct | 49 ms | 106040 KB | Output is correct |
4 | Correct | 43 ms | 106228 KB | Output is correct |
5 | Correct | 105 ms | 112396 KB | Output is correct |
6 | Correct | 43 ms | 106120 KB | Output is correct |
7 | Correct | 44 ms | 106060 KB | Output is correct |
8 | Correct | 110 ms | 111564 KB | Output is correct |
9 | Correct | 108 ms | 112056 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 43 ms | 106024 KB | Output is correct |
2 | Correct | 42 ms | 106072 KB | Output is correct |
3 | Correct | 44 ms | 106132 KB | Output is correct |
4 | Correct | 43 ms | 106012 KB | Output is correct |
5 | Correct | 49 ms | 106040 KB | Output is correct |
6 | Correct | 54 ms | 106060 KB | Output is correct |
7 | Correct | 43 ms | 106000 KB | Output is correct |
8 | Correct | 44 ms | 106020 KB | Output is correct |
9 | Correct | 42 ms | 106144 KB | Output is correct |
10 | Correct | 43 ms | 106124 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 50 ms | 106148 KB | Output is correct |
2 | Correct | 49 ms | 106172 KB | Output is correct |
3 | Correct | 53 ms | 106224 KB | Output is correct |
4 | Correct | 48 ms | 106172 KB | Output is correct |
5 | Correct | 48 ms | 106228 KB | Output is correct |
6 | Correct | 49 ms | 106240 KB | Output is correct |
7 | Correct | 44 ms | 106172 KB | Output is correct |
8 | Correct | 44 ms | 106236 KB | Output is correct |
9 | Correct | 45 ms | 106316 KB | Output is correct |
10 | Correct | 48 ms | 106180 KB | Output is correct |
11 | Correct | 47 ms | 106188 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 42 ms | 106072 KB | Output is correct |
2 | Correct | 45 ms | 106040 KB | Output is correct |
3 | Correct | 49 ms | 106040 KB | Output is correct |
4 | Correct | 43 ms | 106228 KB | Output is correct |
5 | Correct | 105 ms | 112396 KB | Output is correct |
6 | Correct | 43 ms | 106120 KB | Output is correct |
7 | Correct | 44 ms | 106060 KB | Output is correct |
8 | Correct | 110 ms | 111564 KB | Output is correct |
9 | Correct | 108 ms | 112056 KB | Output is correct |
10 | Correct | 43 ms | 106024 KB | Output is correct |
11 | Correct | 42 ms | 106072 KB | Output is correct |
12 | Correct | 44 ms | 106132 KB | Output is correct |
13 | Correct | 43 ms | 106012 KB | Output is correct |
14 | Correct | 49 ms | 106040 KB | Output is correct |
15 | Correct | 54 ms | 106060 KB | Output is correct |
16 | Correct | 43 ms | 106000 KB | Output is correct |
17 | Correct | 44 ms | 106020 KB | Output is correct |
18 | Correct | 42 ms | 106144 KB | Output is correct |
19 | Correct | 43 ms | 106124 KB | Output is correct |
20 | Correct | 50 ms | 106148 KB | Output is correct |
21 | Correct | 49 ms | 106172 KB | Output is correct |
22 | Correct | 53 ms | 106224 KB | Output is correct |
23 | Correct | 48 ms | 106172 KB | Output is correct |
24 | Correct | 48 ms | 106228 KB | Output is correct |
25 | Correct | 49 ms | 106240 KB | Output is correct |
26 | Correct | 44 ms | 106172 KB | Output is correct |
27 | Correct | 44 ms | 106236 KB | Output is correct |
28 | Correct | 45 ms | 106316 KB | Output is correct |
29 | Correct | 48 ms | 106180 KB | Output is correct |
30 | Correct | 47 ms | 106188 KB | Output is correct |
31 | Correct | 109 ms | 112624 KB | Output is correct |
32 | Correct | 252 ms | 111892 KB | Output is correct |
33 | Correct | 113 ms | 112324 KB | Output is correct |
34 | Correct | 111 ms | 112600 KB | Output is correct |
35 | Correct | 118 ms | 113516 KB | Output is correct |
36 | Correct | 113 ms | 113124 KB | Output is correct |
37 | Correct | 129 ms | 113468 KB | Output is correct |
38 | Correct | 114 ms | 113072 KB | Output is correct |
39 | Correct | 122 ms | 111008 KB | Output is correct |
40 | Correct | 107 ms | 112956 KB | Output is correct |
41 | Correct | 111 ms | 112500 KB | Output is correct |
42 | Correct | 118 ms | 111572 KB | Output is correct |
43 | Correct | 109 ms | 113392 KB | Output is correct |
44 | Correct | 122 ms | 113536 KB | Output is correct |
45 | Correct | 113 ms | 112332 KB | Output is correct |
46 | Correct | 109 ms | 113356 KB | Output is correct |
47 | Correct | 118 ms | 112836 KB | Output is correct |
48 | Correct | 113 ms | 111692 KB | Output is correct |
49 | Correct | 107 ms | 111944 KB | Output is correct |
50 | Correct | 112 ms | 110808 KB | Output is correct |
51 | Correct | 135 ms | 111948 KB | Output is correct |
52 | Correct | 226 ms | 110912 KB | Output is correct |
53 | Correct | 193 ms | 110972 KB | Output is correct |
54 | Correct | 114 ms | 110804 KB | Output is correct |
55 | Correct | 120 ms | 110916 KB | Output is correct |
56 | Correct | 149 ms | 111176 KB | Output is correct |
57 | Correct | 128 ms | 111312 KB | Output is correct |
58 | Correct | 126 ms | 111184 KB | Output is correct |