# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
362708 | 2021-02-04T07:32:07 Z | wind_reaper | Bank (IZhO14_bank) | C++17 | 639 ms | 90468 KB |
#include <bits/stdc++.h> using namespace std; const int MXN = 20; const int MX = 1000; vector<int> pos[MXN*MX+1]; vector<vector<int>> dp(MXN, vector<int>(1 << MXN, -1)); int n, m; vector<int> a; bool solve(int idx, int mask){ if(idx == n) return 1; if(dp[idx][mask] != -1){ return dp[idx][mask]; } bool ans = 0; for(int nmask : pos[a[idx]]){ if((nmask & mask) == 0) ans = ans | solve(idx+1, mask|nmask); } return dp[idx][mask] = ans; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); //dp[i][mask] -> is it possible to cover all employees till i using mask notes cin >> n >> m; a.resize(n); for(int i = 0; i < n; i++) cin >> a[i]; vector<int> b(m); for(int i = 0; i < m; i++) cin >> b[i]; for(int mask = 0; mask < (1 << m); mask++){ int sum = 0; for(int i = 0; i < m; i++) if(mask & (1 << i)) sum += b[i]; pos[sum].push_back(mask); } cout << (solve(0, 0) ? "YES" : "NO") << '\n'; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 49 ms | 87020 KB | Output is correct |
2 | Correct | 50 ms | 87020 KB | Output is correct |
3 | Correct | 50 ms | 87020 KB | Output is correct |
4 | Correct | 54 ms | 87020 KB | Output is correct |
5 | Correct | 119 ms | 89316 KB | Output is correct |
6 | Correct | 49 ms | 87020 KB | Output is correct |
7 | Correct | 53 ms | 87020 KB | Output is correct |
8 | Correct | 128 ms | 88420 KB | Output is correct |
9 | Correct | 119 ms | 88804 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 51 ms | 87020 KB | Output is correct |
2 | Correct | 53 ms | 87148 KB | Output is correct |
3 | Correct | 59 ms | 87020 KB | Output is correct |
4 | Correct | 50 ms | 87148 KB | Output is correct |
5 | Correct | 50 ms | 87020 KB | Output is correct |
6 | Correct | 51 ms | 87020 KB | Output is correct |
7 | Correct | 50 ms | 87020 KB | Output is correct |
8 | Correct | 50 ms | 87020 KB | Output is correct |
9 | Correct | 52 ms | 87020 KB | Output is correct |
10 | Correct | 52 ms | 87020 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 51 ms | 87020 KB | Output is correct |
2 | Correct | 54 ms | 87020 KB | Output is correct |
3 | Correct | 52 ms | 87040 KB | Output is correct |
4 | Correct | 57 ms | 87020 KB | Output is correct |
5 | Correct | 51 ms | 87276 KB | Output is correct |
6 | Correct | 52 ms | 87020 KB | Output is correct |
7 | Correct | 52 ms | 87020 KB | Output is correct |
8 | Correct | 51 ms | 87020 KB | Output is correct |
9 | Correct | 52 ms | 87172 KB | Output is correct |
10 | Correct | 52 ms | 87020 KB | Output is correct |
11 | Correct | 51 ms | 87020 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 49 ms | 87020 KB | Output is correct |
2 | Correct | 50 ms | 87020 KB | Output is correct |
3 | Correct | 50 ms | 87020 KB | Output is correct |
4 | Correct | 54 ms | 87020 KB | Output is correct |
5 | Correct | 119 ms | 89316 KB | Output is correct |
6 | Correct | 49 ms | 87020 KB | Output is correct |
7 | Correct | 53 ms | 87020 KB | Output is correct |
8 | Correct | 128 ms | 88420 KB | Output is correct |
9 | Correct | 119 ms | 88804 KB | Output is correct |
10 | Correct | 51 ms | 87020 KB | Output is correct |
11 | Correct | 53 ms | 87148 KB | Output is correct |
12 | Correct | 59 ms | 87020 KB | Output is correct |
13 | Correct | 50 ms | 87148 KB | Output is correct |
14 | Correct | 50 ms | 87020 KB | Output is correct |
15 | Correct | 51 ms | 87020 KB | Output is correct |
16 | Correct | 50 ms | 87020 KB | Output is correct |
17 | Correct | 50 ms | 87020 KB | Output is correct |
18 | Correct | 52 ms | 87020 KB | Output is correct |
19 | Correct | 52 ms | 87020 KB | Output is correct |
20 | Correct | 51 ms | 87020 KB | Output is correct |
21 | Correct | 54 ms | 87020 KB | Output is correct |
22 | Correct | 52 ms | 87040 KB | Output is correct |
23 | Correct | 57 ms | 87020 KB | Output is correct |
24 | Correct | 51 ms | 87276 KB | Output is correct |
25 | Correct | 52 ms | 87020 KB | Output is correct |
26 | Correct | 52 ms | 87020 KB | Output is correct |
27 | Correct | 51 ms | 87020 KB | Output is correct |
28 | Correct | 52 ms | 87172 KB | Output is correct |
29 | Correct | 52 ms | 87020 KB | Output is correct |
30 | Correct | 51 ms | 87020 KB | Output is correct |
31 | Correct | 143 ms | 89444 KB | Output is correct |
32 | Correct | 169 ms | 88804 KB | Output is correct |
33 | Correct | 127 ms | 89188 KB | Output is correct |
34 | Correct | 140 ms | 89572 KB | Output is correct |
35 | Correct | 134 ms | 90468 KB | Output is correct |
36 | Correct | 127 ms | 89956 KB | Output is correct |
37 | Correct | 130 ms | 90340 KB | Output is correct |
38 | Correct | 146 ms | 90084 KB | Output is correct |
39 | Correct | 143 ms | 89060 KB | Output is correct |
40 | Correct | 126 ms | 89956 KB | Output is correct |
41 | Correct | 129 ms | 89536 KB | Output is correct |
42 | Correct | 122 ms | 88548 KB | Output is correct |
43 | Correct | 124 ms | 90340 KB | Output is correct |
44 | Correct | 131 ms | 90468 KB | Output is correct |
45 | Correct | 122 ms | 89188 KB | Output is correct |
46 | Correct | 122 ms | 90340 KB | Output is correct |
47 | Correct | 131 ms | 89828 KB | Output is correct |
48 | Correct | 123 ms | 88676 KB | Output is correct |
49 | Correct | 119 ms | 88804 KB | Output is correct |
50 | Correct | 346 ms | 88932 KB | Output is correct |
51 | Correct | 120 ms | 88932 KB | Output is correct |
52 | Correct | 125 ms | 88548 KB | Output is correct |
53 | Correct | 639 ms | 88804 KB | Output is correct |
54 | Correct | 407 ms | 88932 KB | Output is correct |
55 | Correct | 362 ms | 88936 KB | Output is correct |
56 | Correct | 378 ms | 90084 KB | Output is correct |
57 | Correct | 408 ms | 90212 KB | Output is correct |
58 | Correct | 385 ms | 90212 KB | Output is correct |