#include <iostream>
#include <vector>
#define MAX_N 20
#define MAX_M 20
using namespace std;
int s[MAX_M], b[MAX_N], sePoate[MAX_M][1 << MAX_N];
vector <int> sol[MAX_M];
int main() {
int m, n, suma, mask, i, j;
cin >> m >> n;
for ( i = 0; i < m; i++ )
cin >> s[i];
for ( i = 0; i < n; i++ )
cin >> b[i];
for ( mask = 0; mask < (1 << n); mask++ ) {
suma = 0;
for ( i = 0; i < n; i++ ) {
if ( (mask >> i) & 1 )
suma += b[i];
}
for ( i = 0; i < m; i++ ) {
if ( s[i] == suma )
sol[i].push_back( mask );
}
}
for ( i = 0; i < sol[0].size(); i++ )
sePoate[0][sol[0][i]] = 1;
for ( i = 1; i < m; i++ ) {
for ( mask = 0; mask < (1 << n); mask++ ) {
if ( sePoate[i - 1][mask] ) {
for ( j = 0; j < sol[i].size(); j++ ) {
if ( (mask & sol[i][j]) == 0 )
sePoate[i][mask + sol[i][j]] = 1;
}
}
}
}
mask = 0;
while ( mask < (1 << n) && !sePoate[m - 1][mask] )
mask++;
if ( mask == (1 << n) )
cout << "NO";
else
cout << "YES";
return 0;
}
Compilation message
bank.cpp: In function 'int main()':
bank.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for ( i = 0; i < sol[0].size(); i++ )
| ~~^~~~~~~~~~~~~~~
bank.cpp:38:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for ( j = 0; j < sol[i].size(); j++ ) {
| ~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
332 KB |
Output is correct |
5 |
Correct |
60 ms |
276 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
60 ms |
4292 KB |
Output is correct |
9 |
Correct |
60 ms |
284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
2 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
332 KB |
Output is correct |
5 |
Correct |
60 ms |
276 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
60 ms |
4292 KB |
Output is correct |
9 |
Correct |
60 ms |
284 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
2 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
61 ms |
2372 KB |
Output is correct |
32 |
Correct |
128 ms |
7992 KB |
Output is correct |
33 |
Correct |
73 ms |
1824 KB |
Output is correct |
34 |
Correct |
78 ms |
452 KB |
Output is correct |
35 |
Correct |
80 ms |
548 KB |
Output is correct |
36 |
Correct |
93 ms |
404 KB |
Output is correct |
37 |
Correct |
60 ms |
324 KB |
Output is correct |
38 |
Correct |
63 ms |
292 KB |
Output is correct |
39 |
Correct |
86 ms |
16672 KB |
Output is correct |
40 |
Correct |
74 ms |
280 KB |
Output is correct |
41 |
Correct |
100 ms |
420 KB |
Output is correct |
42 |
Correct |
74 ms |
10308 KB |
Output is correct |
43 |
Correct |
70 ms |
1060 KB |
Output is correct |
44 |
Correct |
83 ms |
292 KB |
Output is correct |
45 |
Correct |
64 ms |
8620 KB |
Output is correct |
46 |
Correct |
68 ms |
3872 KB |
Output is correct |
47 |
Correct |
84 ms |
408 KB |
Output is correct |
48 |
Correct |
62 ms |
3752 KB |
Output is correct |
49 |
Correct |
59 ms |
280 KB |
Output is correct |
50 |
Correct |
180 ms |
54700 KB |
Output is correct |
51 |
Correct |
78 ms |
576 KB |
Output is correct |
52 |
Correct |
83 ms |
6584 KB |
Output is correct |
53 |
Correct |
452 ms |
28476 KB |
Output is correct |
54 |
Correct |
210 ms |
52220 KB |
Output is correct |
55 |
Correct |
174 ms |
54624 KB |
Output is correct |
56 |
Correct |
171 ms |
54428 KB |
Output is correct |
57 |
Correct |
175 ms |
50624 KB |
Output is correct |
58 |
Correct |
178 ms |
50572 KB |
Output is correct |