# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
141557 |
2019-08-08T11:52:44 Z |
meatrow |
Bank (IZhO14_bank) |
C++17 |
|
277 ms |
17796 KB |
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 20;
const int N = 1 << M;
const int V = 1001;
vector<int> g[V];
vector<int> lst[M];
int dp[M][N];
int s[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < m; i++) {
cin >> b[i];
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int it1 = 0, it2 = 0;
while (it1 < a.size() && it2 < b.size()) {
if (a[it1] == b[it2]) {
a.erase(a.begin() + it1);
b.erase(b.begin() + it2);
continue;
}
if (a[it1] < b[it2]) {
it1++;
} else {
it2++;
}
}
if (a.empty()) {
cout << "YES";
return 0;
}
n = a.size();
m = b.size();
int topkek = 1 << m;
for (int mask = 1; mask < topkek; mask++) {
int cnt = 0;
for (int i = 0; i < m; i++) {
if (mask & (1 << i)) {
s[mask] += b[i];
cnt++;
}
}
if (s[mask] < V) {
g[s[mask]].push_back(mask);
}
if (s[mask] == a[0]) {
dp[0][mask] = 1;
}
lst[cnt].push_back(mask);
}
for (int i = 1; i < n; i++) {
for (int cnt = i * 2; cnt <= m; cnt++) {
for (int mask : lst[cnt]) {
if (!dp[i - 1][mask]) {
continue;
}
for (int kek = mask; kek < topkek; kek = (kek + 1) | mask) {
if (s[mask ^ kek] == a[i]) {
dp[i][kek] = 1;
}
}
}
}
}
for (int i = 0; i < topkek; i++) {
if (dp[n - 1][i]) {
cout << "YES";
return 0;
}
}
cout << "NO";
return 0;
}
Compilation message
bank.cpp: In function 'int main()':
bank.cpp:35:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (it1 < a.size() && it2 < b.size()) {
~~~~^~~~~~~~~~
bank.cpp:35:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (it1 < a.size() && it2 < b.size()) {
~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
888 KB |
Output is correct |
5 |
Correct |
110 ms |
15192 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
108 ms |
17276 KB |
Output is correct |
9 |
Correct |
107 ms |
14664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
632 KB |
Output is correct |
2 |
Correct |
4 ms |
632 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
476 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
4 ms |
504 KB |
Output is correct |
7 |
Correct |
4 ms |
636 KB |
Output is correct |
8 |
Correct |
4 ms |
632 KB |
Output is correct |
9 |
Correct |
3 ms |
552 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
14 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
888 KB |
Output is correct |
5 |
Correct |
110 ms |
15192 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
108 ms |
17276 KB |
Output is correct |
9 |
Correct |
107 ms |
14664 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
4 ms |
632 KB |
Output is correct |
21 |
Correct |
4 ms |
632 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
2 ms |
476 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
4 ms |
504 KB |
Output is correct |
26 |
Correct |
4 ms |
636 KB |
Output is correct |
27 |
Correct |
4 ms |
632 KB |
Output is correct |
28 |
Correct |
3 ms |
552 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
30 |
Correct |
14 ms |
632 KB |
Output is correct |
31 |
Correct |
113 ms |
14280 KB |
Output is correct |
32 |
Correct |
193 ms |
15288 KB |
Output is correct |
33 |
Correct |
116 ms |
10568 KB |
Output is correct |
34 |
Correct |
56 ms |
5084 KB |
Output is correct |
35 |
Correct |
28 ms |
2796 KB |
Output is correct |
36 |
Correct |
2 ms |
376 KB |
Output is correct |
37 |
Correct |
100 ms |
9680 KB |
Output is correct |
38 |
Correct |
104 ms |
9480 KB |
Output is correct |
39 |
Correct |
2 ms |
376 KB |
Output is correct |
40 |
Correct |
114 ms |
10868 KB |
Output is correct |
41 |
Correct |
56 ms |
5108 KB |
Output is correct |
42 |
Correct |
149 ms |
15184 KB |
Output is correct |
43 |
Correct |
120 ms |
11532 KB |
Output is correct |
44 |
Correct |
2 ms |
348 KB |
Output is correct |
45 |
Correct |
137 ms |
17796 KB |
Output is correct |
46 |
Correct |
119 ms |
12744 KB |
Output is correct |
47 |
Correct |
2 ms |
476 KB |
Output is correct |
48 |
Correct |
107 ms |
16244 KB |
Output is correct |
49 |
Correct |
109 ms |
14664 KB |
Output is correct |
50 |
Correct |
2 ms |
376 KB |
Output is correct |
51 |
Correct |
73 ms |
7572 KB |
Output is correct |
52 |
Correct |
277 ms |
15840 KB |
Output is correct |
53 |
Correct |
17 ms |
1656 KB |
Output is correct |
54 |
Correct |
2 ms |
376 KB |
Output is correct |
55 |
Correct |
2 ms |
380 KB |
Output is correct |
56 |
Correct |
5 ms |
376 KB |
Output is correct |
57 |
Correct |
2 ms |
376 KB |
Output is correct |
58 |
Correct |
2 ms |
376 KB |
Output is correct |