# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
166046 |
2019-11-30T12:06:42 Z |
GioChkhaidze |
Bank (IZhO14_bank) |
C++14 |
|
895 ms |
13944 KB |
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,S0,S1,S2,i,j,mask;
int a[22],b[22],f1[1002],f2[1002];
int F1[1058576],F3[1058576],F2[1058576];
bool ans[1058576];
main () {
cin>>n>>m;
for (i=0; i<n; i++) {
cin>>a[i];
f1[a[i]]++;
}
for (i=0; i<m; i++) {
cin>>b[i];
f2[b[i]]++;
}
n=0,m=0;
for (i=1; i<=1000; i++)
if (f1[i]>f2[i]) {
for (j=f2[i]+1; j<=f1[i]; j++)
a[n++]=i,S1+=i;
}
else {
for (j=f1[i]+1; j<=f2[i]; j++)
b[m++]=i;
}
if (!n) {
cout<<"YES\n";
return 0;
}
int M=(1<<m);
for (j=0; j<n; j++) {
for (mask=0; mask<M; ++mask) {
S0=0;
for (i=0; i<m; i++)
if ((mask>>i)&1) {
S0+=b[i];
if (S0>a[j]) break;
}
if (S0==a[j]) F2[mask]=1;
}
for (i=0; i<m; ++i)
for (mask=0; mask<M; ++mask)
if (mask & (1<<i))
F2[mask]+=F2[mask^(1<<i)];
for (mask=0; mask<M; ++mask) {
if (!j) F3[mask]=F2[mask];
else F3[mask]=F1[mask]*F2[mask];
F1[mask]=F3[mask];
}
for (i=m-1; i>=0; --i)
for (mask=(1<<m)-1; mask>=0; --mask)
if (mask & (1<<i))
F3[mask]-=F3[mask^(1<<i)];
for (mask=0; mask<M; ++mask)
ans[mask]|=F3[mask],F2[mask]=0;
}
for (mask=M-1; mask>=0; --mask)
if (ans[mask]) {
S2=0;
for (i=0; i<m; i++)
if ((mask>>i)&1) S2+=b[i];
if (S1==S2) { cout<<"YES\n"; return 0; }
}
cout<<"NO\n";
}
Compilation message
bank.cpp:10:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main () {
^
bank.cpp: In function 'int main()':
bank.cpp:53:6: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (i=0; i<m; ++i)
^~~
bank.cpp:58:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (mask=0; mask<M; ++mask) {
^~~
# |
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 |
6 ms |
760 KB |
Output is correct |
5 |
Correct |
75 ms |
13688 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
140 ms |
13688 KB |
Output is correct |
9 |
Correct |
141 ms |
13688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
380 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 |
348 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 |
9 ms |
604 KB |
Output is correct |
2 |
Correct |
7 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
4 ms |
376 KB |
Output is correct |
6 |
Correct |
6 ms |
632 KB |
Output is correct |
7 |
Correct |
8 ms |
504 KB |
Output is correct |
8 |
Correct |
7 ms |
632 KB |
Output is correct |
9 |
Correct |
3 ms |
376 KB |
Output is correct |
10 |
Correct |
3 ms |
380 KB |
Output is correct |
11 |
Correct |
26 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 |
6 ms |
760 KB |
Output is correct |
5 |
Correct |
75 ms |
13688 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
140 ms |
13688 KB |
Output is correct |
9 |
Correct |
141 ms |
13688 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
380 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 |
348 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 |
9 ms |
604 KB |
Output is correct |
21 |
Correct |
7 ms |
504 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
4 ms |
376 KB |
Output is correct |
25 |
Correct |
6 ms |
632 KB |
Output is correct |
26 |
Correct |
8 ms |
504 KB |
Output is correct |
27 |
Correct |
7 ms |
632 KB |
Output is correct |
28 |
Correct |
3 ms |
376 KB |
Output is correct |
29 |
Correct |
3 ms |
380 KB |
Output is correct |
30 |
Correct |
26 ms |
632 KB |
Output is correct |
31 |
Correct |
269 ms |
13796 KB |
Output is correct |
32 |
Correct |
397 ms |
13716 KB |
Output is correct |
33 |
Correct |
800 ms |
13760 KB |
Output is correct |
34 |
Correct |
317 ms |
7032 KB |
Output is correct |
35 |
Correct |
214 ms |
3832 KB |
Output is correct |
36 |
Correct |
2 ms |
376 KB |
Output is correct |
37 |
Correct |
177 ms |
13692 KB |
Output is correct |
38 |
Correct |
266 ms |
13816 KB |
Output is correct |
39 |
Correct |
2 ms |
376 KB |
Output is correct |
40 |
Correct |
668 ms |
13816 KB |
Output is correct |
41 |
Correct |
646 ms |
7160 KB |
Output is correct |
42 |
Correct |
660 ms |
13816 KB |
Output is correct |
43 |
Correct |
873 ms |
13692 KB |
Output is correct |
44 |
Correct |
5 ms |
376 KB |
Output is correct |
45 |
Correct |
354 ms |
13816 KB |
Output is correct |
46 |
Correct |
719 ms |
13816 KB |
Output is correct |
47 |
Correct |
2 ms |
376 KB |
Output is correct |
48 |
Correct |
139 ms |
13788 KB |
Output is correct |
49 |
Correct |
80 ms |
13688 KB |
Output is correct |
50 |
Correct |
2 ms |
276 KB |
Output is correct |
51 |
Correct |
577 ms |
7104 KB |
Output is correct |
52 |
Correct |
895 ms |
13944 KB |
Output is correct |
53 |
Correct |
35 ms |
1144 KB |
Output is correct |
54 |
Correct |
2 ms |
376 KB |
Output is correct |
55 |
Correct |
2 ms |
376 KB |
Output is correct |
56 |
Correct |
2 ms |
376 KB |
Output is correct |
57 |
Correct |
2 ms |
376 KB |
Output is correct |
58 |
Correct |
2 ms |
376 KB |
Output is correct |