# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
758994 |
2023-06-15T16:24:25 Z |
scrge |
Bank (IZhO14_bank) |
C++17 |
|
309 ms |
26288 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 20;
int n, m;
int salary[N], notes[N], pref[N+1];
int dp[1 << N], sum[1 << N];
signed main(){
cin >> n >> m;
int cur_pref = 0;
pref[0] = 0;
for(int i = 0; i < n; i++){
cin >> salary[i];
//cur_pref += salary[i];
pref[i+1] = pref[i] + salary[i];
}
for(int i = 0; i < m; i++){
cin >> notes[i];
}
for(int i = 0; i < (1 << m); i++){
int cur = 0;
for(int j = 0; j < m; j++){
if(i & (1 << j)) cur += notes[j];
}
sum[i] = cur;
}
vector<int> masks[N+1];
for(int i = 0; i < (1 << m); i++)
masks[__builtin_popcount(i)].push_back(i);
memset(dp, 0, sizeof dp);
dp[0] = true;
for(int i = 0; i < m; i++){
for(int mask: masks[i]){
for(int j = 0; j < m; j++){
if((mask & (1 << j)) || !dp[mask]) continue;
int nmask = mask | (1 << j);
auto lb1 = upper_bound(pref, pref+n, sum[mask]);
auto lb2 = upper_bound(pref, pref+n, sum[nmask]);
lb1--, lb2--;
if(lb1 != lb2){
if(lb2 == next(lb1) && *lb2 == sum[nmask])
dp[nmask] = true;
} else{
dp[nmask] = true;
}
}
//cout << bitset<6>(mask) << " " << dp[mask] << endl;
}
}
bool ans = false;
for(int mask = 0; mask < (1 << m); mask++){
if(sum[mask] == pref[n]){
//printf("mask %d has sum equals %d, dp = %d\n", mask, pref[n], dp[mask]);
}
if(sum[mask] == pref[n] && dp[mask])
ans = true;
}
if(ans)
cout << "YES";
else
cout << "NO";
}
Compilation message
bank.cpp: In function 'int main()':
bank.cpp:12:7: warning: unused variable 'cur_pref' [-Wunused-variable]
12 | int cur_pref = 0;
| ^~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8500 KB |
Output is correct |
2 |
Correct |
3 ms |
8404 KB |
Output is correct |
3 |
Correct |
4 ms |
8496 KB |
Output is correct |
4 |
Correct |
9 ms |
9152 KB |
Output is correct |
5 |
Correct |
188 ms |
26144 KB |
Output is correct |
6 |
Correct |
4 ms |
8532 KB |
Output is correct |
7 |
Correct |
4 ms |
8532 KB |
Output is correct |
8 |
Correct |
188 ms |
26160 KB |
Output is correct |
9 |
Correct |
197 ms |
26128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8532 KB |
Output is correct |
2 |
Correct |
5 ms |
8532 KB |
Output is correct |
3 |
Correct |
4 ms |
8532 KB |
Output is correct |
4 |
Correct |
4 ms |
8532 KB |
Output is correct |
5 |
Correct |
3 ms |
8532 KB |
Output is correct |
6 |
Correct |
3 ms |
8532 KB |
Output is correct |
7 |
Correct |
4 ms |
8532 KB |
Output is correct |
8 |
Correct |
3 ms |
8532 KB |
Output is correct |
9 |
Correct |
3 ms |
8532 KB |
Output is correct |
10 |
Correct |
4 ms |
8496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8760 KB |
Output is correct |
2 |
Correct |
6 ms |
8788 KB |
Output is correct |
3 |
Correct |
5 ms |
8788 KB |
Output is correct |
4 |
Correct |
6 ms |
8720 KB |
Output is correct |
5 |
Correct |
5 ms |
8788 KB |
Output is correct |
6 |
Correct |
5 ms |
8788 KB |
Output is correct |
7 |
Correct |
5 ms |
8744 KB |
Output is correct |
8 |
Correct |
6 ms |
8788 KB |
Output is correct |
9 |
Correct |
6 ms |
8788 KB |
Output is correct |
10 |
Correct |
5 ms |
8756 KB |
Output is correct |
11 |
Correct |
6 ms |
8788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8500 KB |
Output is correct |
2 |
Correct |
3 ms |
8404 KB |
Output is correct |
3 |
Correct |
4 ms |
8496 KB |
Output is correct |
4 |
Correct |
9 ms |
9152 KB |
Output is correct |
5 |
Correct |
188 ms |
26144 KB |
Output is correct |
6 |
Correct |
4 ms |
8532 KB |
Output is correct |
7 |
Correct |
4 ms |
8532 KB |
Output is correct |
8 |
Correct |
188 ms |
26160 KB |
Output is correct |
9 |
Correct |
197 ms |
26128 KB |
Output is correct |
10 |
Correct |
4 ms |
8532 KB |
Output is correct |
11 |
Correct |
5 ms |
8532 KB |
Output is correct |
12 |
Correct |
4 ms |
8532 KB |
Output is correct |
13 |
Correct |
4 ms |
8532 KB |
Output is correct |
14 |
Correct |
3 ms |
8532 KB |
Output is correct |
15 |
Correct |
3 ms |
8532 KB |
Output is correct |
16 |
Correct |
4 ms |
8532 KB |
Output is correct |
17 |
Correct |
3 ms |
8532 KB |
Output is correct |
18 |
Correct |
3 ms |
8532 KB |
Output is correct |
19 |
Correct |
4 ms |
8496 KB |
Output is correct |
20 |
Correct |
5 ms |
8760 KB |
Output is correct |
21 |
Correct |
6 ms |
8788 KB |
Output is correct |
22 |
Correct |
5 ms |
8788 KB |
Output is correct |
23 |
Correct |
6 ms |
8720 KB |
Output is correct |
24 |
Correct |
5 ms |
8788 KB |
Output is correct |
25 |
Correct |
5 ms |
8788 KB |
Output is correct |
26 |
Correct |
5 ms |
8744 KB |
Output is correct |
27 |
Correct |
6 ms |
8788 KB |
Output is correct |
28 |
Correct |
6 ms |
8788 KB |
Output is correct |
29 |
Correct |
5 ms |
8756 KB |
Output is correct |
30 |
Correct |
6 ms |
8788 KB |
Output is correct |
31 |
Correct |
206 ms |
26212 KB |
Output is correct |
32 |
Correct |
245 ms |
26212 KB |
Output is correct |
33 |
Correct |
166 ms |
26124 KB |
Output is correct |
34 |
Correct |
151 ms |
26124 KB |
Output is correct |
35 |
Correct |
150 ms |
26204 KB |
Output is correct |
36 |
Correct |
154 ms |
26212 KB |
Output is correct |
37 |
Correct |
166 ms |
26136 KB |
Output is correct |
38 |
Correct |
149 ms |
26208 KB |
Output is correct |
39 |
Correct |
243 ms |
26188 KB |
Output is correct |
40 |
Correct |
150 ms |
26224 KB |
Output is correct |
41 |
Correct |
147 ms |
26196 KB |
Output is correct |
42 |
Correct |
229 ms |
26216 KB |
Output is correct |
43 |
Correct |
157 ms |
26216 KB |
Output is correct |
44 |
Correct |
150 ms |
26208 KB |
Output is correct |
45 |
Correct |
208 ms |
26216 KB |
Output is correct |
46 |
Correct |
186 ms |
26212 KB |
Output is correct |
47 |
Correct |
177 ms |
26208 KB |
Output is correct |
48 |
Correct |
186 ms |
26128 KB |
Output is correct |
49 |
Correct |
186 ms |
26216 KB |
Output is correct |
50 |
Correct |
309 ms |
26212 KB |
Output is correct |
51 |
Correct |
153 ms |
26196 KB |
Output is correct |
52 |
Correct |
159 ms |
26168 KB |
Output is correct |
53 |
Correct |
288 ms |
26288 KB |
Output is correct |
54 |
Correct |
309 ms |
26168 KB |
Output is correct |
55 |
Correct |
295 ms |
26168 KB |
Output is correct |
56 |
Correct |
307 ms |
26212 KB |
Output is correct |
57 |
Correct |
295 ms |
26216 KB |
Output is correct |
58 |
Correct |
308 ms |
26220 KB |
Output is correct |