#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44
using namespace std;
int sum[20], a[20], b[20];
int nxt[20], prv[20];
int n, m, first;
void bkt(int pos, int cnt) {
if(pos == m) {
if(cnt == n) {
cout << "YES";
exit(0);
}
}
else {
bkt(pos + 1, cnt);
int i = first;
while(i < n) {
if(sum[i] + b[pos] <= a[i]) {
sum[i] += b[pos];
int aux = first;
if(sum[i] == a[i]) {
if(i == first) {
first = nxt[i];
}
else {
nxt[prv[i]] = nxt[i];
prv[nxt[i]] = prv[i];
}
}
bkt(pos + 1, cnt + (sum[i] == a[i]));
first = aux;
if(i != first) {
nxt[prv[i]] = i;
prv[nxt[i]] = i;
}
sum[i] -= b[pos];
}
i = nxt[i];
}
}
}
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(i = 0; i < n; i++) {
cin >> a[i];
}
for(i = 0; i < m; i++) {
cin >> b[i];
}
for(i = 0; i < n; i++) {
prv[i] = i - 1;
nxt[i] = i + 1;
}
first = 0;
sort(b, b + m, greater<int>());
bkt(0, 0);
cout << "NO";
//cin.close();
//cout.close();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
536 KB |
Output is correct |
3 |
Correct |
2 ms |
536 KB |
Output is correct |
4 |
Correct |
2 ms |
536 KB |
Output is correct |
5 |
Correct |
2 ms |
628 KB |
Output is correct |
6 |
Correct |
2 ms |
628 KB |
Output is correct |
7 |
Correct |
2 ms |
628 KB |
Output is correct |
8 |
Correct |
2 ms |
628 KB |
Output is correct |
9 |
Correct |
11 ms |
628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
628 KB |
Output is correct |
2 |
Correct |
3 ms |
628 KB |
Output is correct |
3 |
Correct |
2 ms |
628 KB |
Output is correct |
4 |
Correct |
2 ms |
628 KB |
Output is correct |
5 |
Correct |
2 ms |
628 KB |
Output is correct |
6 |
Correct |
2 ms |
628 KB |
Output is correct |
7 |
Correct |
3 ms |
628 KB |
Output is correct |
8 |
Correct |
8 ms |
720 KB |
Output is correct |
9 |
Correct |
4 ms |
720 KB |
Output is correct |
10 |
Correct |
11 ms |
720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1077 ms |
720 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
536 KB |
Output is correct |
3 |
Correct |
2 ms |
536 KB |
Output is correct |
4 |
Correct |
2 ms |
536 KB |
Output is correct |
5 |
Correct |
2 ms |
628 KB |
Output is correct |
6 |
Correct |
2 ms |
628 KB |
Output is correct |
7 |
Correct |
2 ms |
628 KB |
Output is correct |
8 |
Correct |
2 ms |
628 KB |
Output is correct |
9 |
Correct |
11 ms |
628 KB |
Output is correct |
10 |
Correct |
7 ms |
628 KB |
Output is correct |
11 |
Correct |
3 ms |
628 KB |
Output is correct |
12 |
Correct |
2 ms |
628 KB |
Output is correct |
13 |
Correct |
2 ms |
628 KB |
Output is correct |
14 |
Correct |
2 ms |
628 KB |
Output is correct |
15 |
Correct |
2 ms |
628 KB |
Output is correct |
16 |
Correct |
3 ms |
628 KB |
Output is correct |
17 |
Correct |
8 ms |
720 KB |
Output is correct |
18 |
Correct |
4 ms |
720 KB |
Output is correct |
19 |
Correct |
11 ms |
720 KB |
Output is correct |
20 |
Execution timed out |
1077 ms |
720 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |