# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
565561 | 2022-05-21T06:12:04 Z | racsosabe | Bank (IZhO14_bank) | C++14 | 158 ms | 10528 KB |
#include<bits/stdc++.h> using namespace::std; const int N = 20 + 5; const int MAX = 1000 * 20 + 5; const int MASK = 1 << 20; int n; int m; int a[N]; int b[N]; int nxt[MAX]; int sum[MASK]; int memo[MASK]; bool vis[MASK]; void preprocess(){ for(int i = 0; i < n; i++){ nxt[a[i]] = a[i]; } int last = MAX; for(int i = MAX - 1; i >= 0; i--){ if(nxt[i] == i) last = i; nxt[i] = last; } for(int mask = 1; mask < 1 << m; mask++){ sum[mask] = sum[mask & (mask - 1)] + b[__builtin_ctz(mask)]; } } bool solve(){ queue<int> Q; Q.emplace(0); while(!Q.empty()){ int mask = Q.front(); Q.pop(); for(int i = 0, p = 1; i < m; i++, p <<= 1){ if(mask & p) continue; int new_sum = sum[mask] + b[i]; if(new_sum == nxt[sum[mask] + 1]) memo[mask | p] = max(memo[mask | p], 1 + memo[mask]); else memo[mask | p] = max(memo[mask | p], memo[mask]); if(not vis[mask | p]){ vis[mask | p] = true; Q.emplace(mask | p); } } } return *max_element(memo, memo + (1 << m)) == n; } int main(){ scanf("%d %d", &n, &m); for(int i = 0; i < n; i++) scanf("%d", a + i); for(int i = 0; i < m; i++) scanf("%d", b + i); for(int i = 1; i < n; i++) a[i] += a[i - 1]; preprocess(); puts(solve() ? "YES" : "NO"); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 3 ms | 724 KB | Output is correct |
5 | Correct | 154 ms | 10400 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 155 ms | 10448 KB | Output is correct |
9 | Correct | 158 ms | 10344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 0 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 | 2 ms | 468 KB | Output is correct |
2 | Correct | 2 ms | 468 KB | Output is correct |
3 | Correct | 2 ms | 468 KB | Output is correct |
4 | Correct | 2 ms | 468 KB | Output is correct |
5 | Correct | 2 ms | 468 KB | Output is correct |
6 | Correct | 2 ms | 468 KB | Output is correct |
7 | Correct | 2 ms | 468 KB | Output is correct |
8 | Correct | 2 ms | 468 KB | Output is correct |
9 | Correct | 2 ms | 468 KB | Output is correct |
10 | Correct | 1 ms | 468 KB | Output is correct |
11 | Correct | 1 ms | 468 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 3 ms | 724 KB | Output is correct |
5 | Correct | 154 ms | 10400 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 155 ms | 10448 KB | Output is correct |
9 | Correct | 158 ms | 10344 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 0 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 | 2 ms | 468 KB | Output is correct |
21 | Correct | 2 ms | 468 KB | Output is correct |
22 | Correct | 2 ms | 468 KB | Output is correct |
23 | Correct | 2 ms | 468 KB | Output is correct |
24 | Correct | 2 ms | 468 KB | Output is correct |
25 | Correct | 2 ms | 468 KB | Output is correct |
26 | Correct | 2 ms | 468 KB | Output is correct |
27 | Correct | 2 ms | 468 KB | Output is correct |
28 | Correct | 2 ms | 468 KB | Output is correct |
29 | Correct | 1 ms | 468 KB | Output is correct |
30 | Correct | 1 ms | 468 KB | Output is correct |
31 | Correct | 121 ms | 10388 KB | Output is correct |
32 | Correct | 136 ms | 10484 KB | Output is correct |
33 | Correct | 156 ms | 10380 KB | Output is correct |
34 | Correct | 130 ms | 10396 KB | Output is correct |
35 | Correct | 140 ms | 10396 KB | Output is correct |
36 | Correct | 127 ms | 10400 KB | Output is correct |
37 | Correct | 129 ms | 10528 KB | Output is correct |
38 | Correct | 149 ms | 10284 KB | Output is correct |
39 | Correct | 112 ms | 10292 KB | Output is correct |
40 | Correct | 142 ms | 10396 KB | Output is correct |
41 | Correct | 131 ms | 10412 KB | Output is correct |
42 | Correct | 158 ms | 10384 KB | Output is correct |
43 | Correct | 120 ms | 10396 KB | Output is correct |
44 | Correct | 131 ms | 10396 KB | Output is correct |
45 | Correct | 147 ms | 10380 KB | Output is correct |
46 | Correct | 144 ms | 10392 KB | Output is correct |
47 | Correct | 116 ms | 10316 KB | Output is correct |
48 | Correct | 125 ms | 10316 KB | Output is correct |
49 | Correct | 138 ms | 10400 KB | Output is correct |
50 | Correct | 127 ms | 10300 KB | Output is correct |
51 | Correct | 146 ms | 10388 KB | Output is correct |
52 | Correct | 148 ms | 10316 KB | Output is correct |
53 | Correct | 125 ms | 10396 KB | Output is correct |
54 | Correct | 111 ms | 10372 KB | Output is correct |
55 | Correct | 131 ms | 10400 KB | Output is correct |
56 | Correct | 124 ms | 10444 KB | Output is correct |
57 | Correct | 103 ms | 10388 KB | Output is correct |
58 | Correct | 102 ms | 10400 KB | Output is correct |