# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
727430 | 2023-04-20T16:14:29 Z | josiftepe | Bank (IZhO14_bank) | C++14 | 229 ms | 113484 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 = 1; for(int i = 0; i < masks[salary[at]].size(); i++) { int tmp_mask = masks[salary[at]][i]; if((tmp_mask & bitmask) == tmp_mask) { if(rec(at - 1, bitmask ^ tmp_mask)) { return dp[at][bitmask] = 1; } } } return dp[at][bitmask] = 0; } 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 | 47 ms | 106028 KB | Output is correct |
2 | Correct | 43 ms | 106012 KB | Output is correct |
3 | Correct | 47 ms | 106060 KB | Output is correct |
4 | Correct | 47 ms | 106204 KB | Output is correct |
5 | Correct | 108 ms | 112512 KB | Output is correct |
6 | Correct | 44 ms | 106060 KB | Output is correct |
7 | Correct | 44 ms | 106064 KB | Output is correct |
8 | Correct | 123 ms | 111556 KB | Output is correct |
9 | Correct | 118 ms | 112160 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 43 ms | 106040 KB | Output is correct |
2 | Correct | 42 ms | 106140 KB | Output is correct |
3 | Correct | 47 ms | 106128 KB | Output is correct |
4 | Correct | 44 ms | 106096 KB | Output is correct |
5 | Correct | 45 ms | 106020 KB | Output is correct |
6 | Correct | 42 ms | 106028 KB | Output is correct |
7 | Correct | 43 ms | 105996 KB | Output is correct |
8 | Correct | 45 ms | 106040 KB | Output is correct |
9 | Correct | 44 ms | 106132 KB | Output is correct |
10 | Correct | 44 ms | 106136 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 44 ms | 106212 KB | Output is correct |
2 | Correct | 42 ms | 106188 KB | Output is correct |
3 | Correct | 45 ms | 106320 KB | Output is correct |
4 | Correct | 47 ms | 106168 KB | Output is correct |
5 | Correct | 45 ms | 106324 KB | Output is correct |
6 | Correct | 56 ms | 106168 KB | Output is correct |
7 | Correct | 46 ms | 106156 KB | Output is correct |
8 | Correct | 46 ms | 106212 KB | Output is correct |
9 | Correct | 45 ms | 106168 KB | Output is correct |
10 | Correct | 45 ms | 106220 KB | Output is correct |
11 | Correct | 47 ms | 106208 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 106028 KB | Output is correct |
2 | Correct | 43 ms | 106012 KB | Output is correct |
3 | Correct | 47 ms | 106060 KB | Output is correct |
4 | Correct | 47 ms | 106204 KB | Output is correct |
5 | Correct | 108 ms | 112512 KB | Output is correct |
6 | Correct | 44 ms | 106060 KB | Output is correct |
7 | Correct | 44 ms | 106064 KB | Output is correct |
8 | Correct | 123 ms | 111556 KB | Output is correct |
9 | Correct | 118 ms | 112160 KB | Output is correct |
10 | Correct | 43 ms | 106040 KB | Output is correct |
11 | Correct | 42 ms | 106140 KB | Output is correct |
12 | Correct | 47 ms | 106128 KB | Output is correct |
13 | Correct | 44 ms | 106096 KB | Output is correct |
14 | Correct | 45 ms | 106020 KB | Output is correct |
15 | Correct | 42 ms | 106028 KB | Output is correct |
16 | Correct | 43 ms | 105996 KB | Output is correct |
17 | Correct | 45 ms | 106040 KB | Output is correct |
18 | Correct | 44 ms | 106132 KB | Output is correct |
19 | Correct | 44 ms | 106136 KB | Output is correct |
20 | Correct | 44 ms | 106212 KB | Output is correct |
21 | Correct | 42 ms | 106188 KB | Output is correct |
22 | Correct | 45 ms | 106320 KB | Output is correct |
23 | Correct | 47 ms | 106168 KB | Output is correct |
24 | Correct | 45 ms | 106324 KB | Output is correct |
25 | Correct | 56 ms | 106168 KB | Output is correct |
26 | Correct | 46 ms | 106156 KB | Output is correct |
27 | Correct | 46 ms | 106212 KB | Output is correct |
28 | Correct | 45 ms | 106168 KB | Output is correct |
29 | Correct | 45 ms | 106220 KB | Output is correct |
30 | Correct | 47 ms | 106208 KB | Output is correct |
31 | Correct | 117 ms | 112568 KB | Output is correct |
32 | Correct | 114 ms | 111820 KB | Output is correct |
33 | Correct | 124 ms | 112244 KB | Output is correct |
34 | Correct | 115 ms | 112716 KB | Output is correct |
35 | Correct | 118 ms | 113484 KB | Output is correct |
36 | Correct | 112 ms | 113080 KB | Output is correct |
37 | Correct | 117 ms | 113444 KB | Output is correct |
38 | Correct | 107 ms | 113192 KB | Output is correct |
39 | Correct | 107 ms | 110940 KB | Output is correct |
40 | Correct | 112 ms | 113000 KB | Output is correct |
41 | Correct | 108 ms | 112480 KB | Output is correct |
42 | Correct | 125 ms | 111564 KB | Output is correct |
43 | Correct | 118 ms | 113344 KB | Output is correct |
44 | Correct | 121 ms | 113424 KB | Output is correct |
45 | Correct | 109 ms | 112404 KB | Output is correct |
46 | Correct | 112 ms | 113344 KB | Output is correct |
47 | Correct | 114 ms | 112860 KB | Output is correct |
48 | Correct | 109 ms | 111692 KB | Output is correct |
49 | Correct | 109 ms | 111848 KB | Output is correct |
50 | Correct | 109 ms | 110868 KB | Output is correct |
51 | Correct | 130 ms | 111936 KB | Output is correct |
52 | Correct | 229 ms | 111032 KB | Output is correct |
53 | Correct | 105 ms | 110940 KB | Output is correct |
54 | Correct | 105 ms | 110828 KB | Output is correct |
55 | Correct | 105 ms | 110884 KB | Output is correct |
56 | Correct | 107 ms | 111184 KB | Output is correct |
57 | Correct | 136 ms | 111192 KB | Output is correct |
58 | Correct | 111 ms | 111152 KB | Output is correct |