# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
603266 |
2022-07-23T19:54:10 Z |
arayi |
Bank (IZhO14_bank) |
C++17 |
|
604 ms |
92228 KB |
// Arayi
#include <bits/stdc++.h>
#define fr first
#define sc second
#define MP make_pair
#define ad push_back
#define PB push_back
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
#define lli long long int
#define y1 arayikhalatyan
#define j1 jigglypuff
#define ld long double
#define itn int
#define pir pair<int, int>
#define all(x) (x).begin(), (x).end()
#define str string
#define enl endl
#define en endl
#define cd complex<long double>
#define vcd vector<cd>
#define vii vector<int>
#define vlli vector<lli>
using namespace std;
lli gcd(lli a, lli b) { return (b == 0LL ? a : gcd(b, a % b)); }
ld dist(ld x, ld y1, ld x2, ld y2)
{
return sqrt((x - x2) * (x - x2) + (y1 - y2) * (y1 - y2));
}
lli S(lli a)
{
return (a * (a + 1LL)) / 2;
}
mt19937 rnd(363542);
char vow[] = {'a', 'e', 'i', 'o', 'u'};
int dx[] = {0, -1, 0, 1, -1, -1, 1, 1, 0};
int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1, 0};
char dc[] = {'R', 'D', 'L', 'U'};
const int N = 3e6 + 20;
const lli mod = LLONG_MAX;
const ld pi = acos(-1);
const ld e = 1e-13;
const int T = 200;
lli bp(lli a, lli b = mod - 2LL)
{
lli ret = 1;
while (b)
{
if (b & 1)
ret *= a, ret %= mod;
a *= a;
a %= mod;
b >>= 1;
}
return ret;
}
ostream &operator<<(ostream &c, pir a)
{
c << a.fr << " " << a.sc;
return c;
}
template <class T>
void maxi(T &a, T b)
{
a = max(a, b);
}
template <class T>
void mini(T &a, T b)
{
a = min(a, b);
}
int n, m;
int a[N], b[N];
vii fp[N];
bool dp[21][N], s[N];
int main()
{
fastio;
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < m; i++)
cin >> b[i];
for (int x = 0; x < (1 << m); x++)
{
int sum = 0;
for (int i = 0; i < m; i++)
if ((1 << i) & x)
sum += b[i];
fp[sum].ad(x);
}
dp[0][0] = 1;
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += a[i];
for (int j = 0; j < (1 << m); j++)
s[j] = 0;
for (auto p : fp[sum - a[i]])
s[p] = dp[i][p];
for (int j = 0; j < m; j++)
{
for (int x = (1 << m) - 1; x >= 0; x--)
{
if (((1 << j) & x) || !s[x])
continue;
s[x ^ (1 << j)] = 1;
}
}
for (auto p : fp[sum])
{
if (s[p])
dp[i + 1][p] = 1;
}
}
bool pat = 0;
for (auto p : fp[sum])
if (dp[n][p])
pat = 1;
if (pat)
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}
/*
__
*(><)*
\/ /
||/
--||
||
/\
/ \
/ \
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
70700 KB |
Output is correct |
2 |
Correct |
41 ms |
70740 KB |
Output is correct |
3 |
Correct |
37 ms |
70824 KB |
Output is correct |
4 |
Correct |
37 ms |
71076 KB |
Output is correct |
5 |
Correct |
123 ms |
78156 KB |
Output is correct |
6 |
Correct |
34 ms |
70732 KB |
Output is correct |
7 |
Correct |
35 ms |
70716 KB |
Output is correct |
8 |
Correct |
121 ms |
78368 KB |
Output is correct |
9 |
Correct |
119 ms |
77752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
70916 KB |
Output is correct |
2 |
Correct |
33 ms |
70784 KB |
Output is correct |
3 |
Correct |
34 ms |
70808 KB |
Output is correct |
4 |
Correct |
37 ms |
70752 KB |
Output is correct |
5 |
Correct |
38 ms |
70816 KB |
Output is correct |
6 |
Correct |
35 ms |
70796 KB |
Output is correct |
7 |
Correct |
34 ms |
70812 KB |
Output is correct |
8 |
Correct |
35 ms |
70844 KB |
Output is correct |
9 |
Correct |
34 ms |
70744 KB |
Output is correct |
10 |
Correct |
35 ms |
70868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
71032 KB |
Output is correct |
2 |
Correct |
38 ms |
70968 KB |
Output is correct |
3 |
Correct |
38 ms |
71076 KB |
Output is correct |
4 |
Correct |
38 ms |
70940 KB |
Output is correct |
5 |
Correct |
39 ms |
70992 KB |
Output is correct |
6 |
Correct |
37 ms |
70936 KB |
Output is correct |
7 |
Correct |
37 ms |
70928 KB |
Output is correct |
8 |
Correct |
37 ms |
70996 KB |
Output is correct |
9 |
Correct |
39 ms |
70984 KB |
Output is correct |
10 |
Correct |
40 ms |
70976 KB |
Output is correct |
11 |
Correct |
41 ms |
70892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
70700 KB |
Output is correct |
2 |
Correct |
41 ms |
70740 KB |
Output is correct |
3 |
Correct |
37 ms |
70824 KB |
Output is correct |
4 |
Correct |
37 ms |
71076 KB |
Output is correct |
5 |
Correct |
123 ms |
78156 KB |
Output is correct |
6 |
Correct |
34 ms |
70732 KB |
Output is correct |
7 |
Correct |
35 ms |
70716 KB |
Output is correct |
8 |
Correct |
121 ms |
78368 KB |
Output is correct |
9 |
Correct |
119 ms |
77752 KB |
Output is correct |
10 |
Correct |
40 ms |
70916 KB |
Output is correct |
11 |
Correct |
33 ms |
70784 KB |
Output is correct |
12 |
Correct |
34 ms |
70808 KB |
Output is correct |
13 |
Correct |
37 ms |
70752 KB |
Output is correct |
14 |
Correct |
38 ms |
70816 KB |
Output is correct |
15 |
Correct |
35 ms |
70796 KB |
Output is correct |
16 |
Correct |
34 ms |
70812 KB |
Output is correct |
17 |
Correct |
35 ms |
70844 KB |
Output is correct |
18 |
Correct |
34 ms |
70744 KB |
Output is correct |
19 |
Correct |
35 ms |
70868 KB |
Output is correct |
20 |
Correct |
39 ms |
71032 KB |
Output is correct |
21 |
Correct |
38 ms |
70968 KB |
Output is correct |
22 |
Correct |
38 ms |
71076 KB |
Output is correct |
23 |
Correct |
38 ms |
70940 KB |
Output is correct |
24 |
Correct |
39 ms |
70992 KB |
Output is correct |
25 |
Correct |
37 ms |
70936 KB |
Output is correct |
26 |
Correct |
37 ms |
70928 KB |
Output is correct |
27 |
Correct |
37 ms |
70996 KB |
Output is correct |
28 |
Correct |
39 ms |
70984 KB |
Output is correct |
29 |
Correct |
40 ms |
70976 KB |
Output is correct |
30 |
Correct |
41 ms |
70892 KB |
Output is correct |
31 |
Correct |
150 ms |
79104 KB |
Output is correct |
32 |
Correct |
172 ms |
79520 KB |
Output is correct |
33 |
Correct |
268 ms |
79484 KB |
Output is correct |
34 |
Correct |
336 ms |
78628 KB |
Output is correct |
35 |
Correct |
365 ms |
79428 KB |
Output is correct |
36 |
Correct |
576 ms |
79052 KB |
Output is correct |
37 |
Correct |
149 ms |
79256 KB |
Output is correct |
38 |
Correct |
194 ms |
78956 KB |
Output is correct |
39 |
Correct |
282 ms |
81928 KB |
Output is correct |
40 |
Correct |
333 ms |
78728 KB |
Output is correct |
41 |
Correct |
577 ms |
78284 KB |
Output is correct |
42 |
Correct |
220 ms |
80588 KB |
Output is correct |
43 |
Correct |
286 ms |
79916 KB |
Output is correct |
44 |
Correct |
465 ms |
79324 KB |
Output is correct |
45 |
Correct |
170 ms |
80668 KB |
Output is correct |
46 |
Correct |
242 ms |
81056 KB |
Output is correct |
47 |
Correct |
499 ms |
78732 KB |
Output is correct |
48 |
Correct |
120 ms |
78372 KB |
Output is correct |
49 |
Correct |
121 ms |
77616 KB |
Output is correct |
50 |
Correct |
593 ms |
91836 KB |
Output is correct |
51 |
Correct |
328 ms |
77904 KB |
Output is correct |
52 |
Correct |
332 ms |
80008 KB |
Output is correct |
53 |
Correct |
352 ms |
84656 KB |
Output is correct |
54 |
Correct |
601 ms |
91404 KB |
Output is correct |
55 |
Correct |
594 ms |
91924 KB |
Output is correct |
56 |
Correct |
600 ms |
92228 KB |
Output is correct |
57 |
Correct |
604 ms |
91156 KB |
Output is correct |
58 |
Correct |
585 ms |
91284 KB |
Output is correct |