# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
850550 |
2023-09-16T21:25:10 Z |
moonpay |
Bank (IZhO14_bank) |
C++17 |
|
1000 ms |
11608 KB |
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int maxn = 2e5 + 10;
const int modm = 1e9 + 7;
void print(vector<int> &t) {
for (auto &r: t) {
cout << r << " ";
}
cout << "\n";
}
bool solve(multiset<int> &a, multiset<int> &b, int n, int m) {
vector<int> af, bs;
for (auto z: a) {
af.push_back(z);
}
sort(af.begin(), af.end());
for (auto z: b) {
bs.push_back(z);
}
bool dp[(1 << m)][n + 1];
for (int i = 0; i < (1 << m); i++) {
for (int j = 0; j < n + 1; j++) {
dp[i][j] = false;
}
}
for (int i = 0; i < (1 << m); i++) {
dp[i][0] = true;
}
vector<int> sum(1 << m, 0);
for (int i = 1; i < (1 << m); i++) {
for (int j = 0; j < m; j++) {
if (i & (1 << j)) {
sum[i] = sum[i ^ (1 << j)] + bs[j];
}
}
}
for (int mask = 0; mask < (1 << m); mask++) {
for (int lm = mask; lm > 0; lm = (lm - 1) & mask) {
int sm = sum[lm];
for (int i = 1; i <= n; i++) {
if (sm == af[i - 1]) {
if (dp[mask ^ lm][i - 1]) {
dp[mask][i] = true;
}
}
}
}
}
return dp[(1 << m) - 1][n];
}
int32_t main() {
int n, m;
cin >> n >> m;
multiset<int> f, s, q;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
f.insert(a);
q.insert(a);
}
for (int j = 0; j < m; j++) {
int a;
cin >> a;
s.insert(a);
}
for (auto z: f) {
if (s.find(z) != s.end() && q.find(z) != q.end()) {
q.erase(q.find(z));
n--;
s.erase(s.find(z));
}
}
if (q.size() == 0) {
std::cout << "YES\n";
return 0;
}
if (2 * q.size() > s.size()) {
std::cout << "NO\n";
} else {
if (n == 1) {
bitset<20001> qr;
qr[0] = true;
for (auto z: s) {
qr |= (qr << z);
}
int u;
for (auto z: q) {
u = z;
}
if (qr[u]) {
std::cout << "YES";
} else {
std::cout << "NO";
}
return 0;
}
std::cout << (solve(q, s, q.size(), s.size()) ? "YES" : "NO");
}
}
Compilation message
bank.cpp: In function 'int32_t main()':
bank.cpp:106:21: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
106 | if (qr[u]) {
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
604 KB |
Output is correct |
2 |
Correct |
13 ms |
600 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
17 ms |
600 KB |
Output is correct |
7 |
Correct |
15 ms |
600 KB |
Output is correct |
8 |
Correct |
13 ms |
600 KB |
Output is correct |
9 |
Correct |
3 ms |
344 KB |
Output is correct |
10 |
Correct |
3 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
344 KB |
Output is correct |
20 |
Correct |
22 ms |
604 KB |
Output is correct |
21 |
Correct |
13 ms |
600 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
17 ms |
600 KB |
Output is correct |
26 |
Correct |
15 ms |
600 KB |
Output is correct |
27 |
Correct |
13 ms |
600 KB |
Output is correct |
28 |
Correct |
3 ms |
344 KB |
Output is correct |
29 |
Correct |
3 ms |
344 KB |
Output is correct |
30 |
Correct |
1 ms |
344 KB |
Output is correct |
31 |
Execution timed out |
1025 ms |
11608 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |