#include "bits/stdc++.h"
using namespace std;
#define endl '\n'
#define debug(x) cerr << #x << " == " << (x) << '\n';
#define all(x) begin(x), end(x)
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
template<typename T>
bool chmax(T& x, T y) { return x < y ? (x = y, true) : false; }
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n), k(n);
for (auto& x : a) cin >> x;
for (auto& x : k) cin >> x;
constexpr int K = 20, L = 10;
vector<int> popcount(1 << K);
for (int mask = 1; mask < (1 << K); ++mask) {
popcount[mask] = 1 + popcount[mask & (mask - 1)];
}
int dp[1 << L][1 << L][L + 1];
vector<int> p(n + 1), opt(n + 1);
int m = 0, last = 0;
for (int i = 1; i <= n; ++i) {
int left = a[i - 1] & ((1 << L) - 1), right = a[i - 1] >> L;
for (int mask = 0; mask < (1 << L); ++mask) {
int x = k[i - 1] - popcount[mask & left];
if (0 <= x && x <= L && chmax(opt[i], opt[dp[mask][right][x]])) {
p[i] = dp[mask][right][x];
}
}
++opt[i];
for (int mask = 0; mask < (1 << L); ++mask) {
int x = popcount[mask & right];
int& j = dp[left][mask][x];
if (opt[j] < opt[i]) j = i;
}
if (chmax(m, opt[i])) last = i;
}
vector<int> I;
while (last) {
I.push_back(last);
last = p[last];
}
reverse(all(I));
assert((int)size(I) == m);
cout << m << endl;
for (int j = 0; j < m; ++j) {
cout << I[j] << "\n "[j + 1 < m];
}
exit(0);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
49440 KB |
answer = 4 |
2 |
Correct |
28 ms |
49524 KB |
answer = 1 |
3 |
Correct |
28 ms |
49560 KB |
answer = 2 |
4 |
Correct |
25 ms |
49492 KB |
answer = 1 |
5 |
Correct |
25 ms |
49484 KB |
answer = 2 |
6 |
Correct |
25 ms |
49484 KB |
answer = 1 |
7 |
Correct |
26 ms |
49544 KB |
answer = 1 |
8 |
Correct |
25 ms |
49428 KB |
answer = 3 |
9 |
Correct |
25 ms |
49548 KB |
answer = 2 |
10 |
Correct |
26 ms |
49552 KB |
answer = 3 |
11 |
Correct |
29 ms |
49484 KB |
answer = 2 |
12 |
Correct |
29 ms |
49476 KB |
answer = 3 |
13 |
Correct |
29 ms |
49480 KB |
answer = 2 |
14 |
Correct |
26 ms |
49512 KB |
answer = 1 |
15 |
Correct |
27 ms |
49484 KB |
answer = 1 |
16 |
Correct |
27 ms |
49456 KB |
answer = 1 |
17 |
Correct |
25 ms |
49572 KB |
answer = 1 |
18 |
Runtime error |
84 ms |
100304 KB |
Execution killed with signal 11 |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
49440 KB |
answer = 4 |
2 |
Correct |
28 ms |
49524 KB |
answer = 1 |
3 |
Correct |
28 ms |
49560 KB |
answer = 2 |
4 |
Correct |
25 ms |
49492 KB |
answer = 1 |
5 |
Correct |
25 ms |
49484 KB |
answer = 2 |
6 |
Correct |
25 ms |
49484 KB |
answer = 1 |
7 |
Correct |
26 ms |
49544 KB |
answer = 1 |
8 |
Correct |
25 ms |
49428 KB |
answer = 3 |
9 |
Correct |
25 ms |
49548 KB |
answer = 2 |
10 |
Correct |
26 ms |
49552 KB |
answer = 3 |
11 |
Correct |
29 ms |
49484 KB |
answer = 2 |
12 |
Correct |
29 ms |
49476 KB |
answer = 3 |
13 |
Correct |
29 ms |
49480 KB |
answer = 2 |
14 |
Correct |
26 ms |
49512 KB |
answer = 1 |
15 |
Correct |
27 ms |
49484 KB |
answer = 1 |
16 |
Correct |
27 ms |
49456 KB |
answer = 1 |
17 |
Correct |
25 ms |
49572 KB |
answer = 1 |
18 |
Runtime error |
84 ms |
100304 KB |
Execution killed with signal 11 |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
49440 KB |
answer = 4 |
2 |
Correct |
28 ms |
49524 KB |
answer = 1 |
3 |
Correct |
28 ms |
49560 KB |
answer = 2 |
4 |
Correct |
25 ms |
49492 KB |
answer = 1 |
5 |
Correct |
25 ms |
49484 KB |
answer = 2 |
6 |
Correct |
25 ms |
49484 KB |
answer = 1 |
7 |
Correct |
26 ms |
49544 KB |
answer = 1 |
8 |
Correct |
25 ms |
49428 KB |
answer = 3 |
9 |
Correct |
25 ms |
49548 KB |
answer = 2 |
10 |
Correct |
26 ms |
49552 KB |
answer = 3 |
11 |
Correct |
29 ms |
49484 KB |
answer = 2 |
12 |
Correct |
29 ms |
49476 KB |
answer = 3 |
13 |
Correct |
29 ms |
49480 KB |
answer = 2 |
14 |
Correct |
26 ms |
49512 KB |
answer = 1 |
15 |
Correct |
27 ms |
49484 KB |
answer = 1 |
16 |
Correct |
27 ms |
49456 KB |
answer = 1 |
17 |
Correct |
25 ms |
49572 KB |
answer = 1 |
18 |
Runtime error |
84 ms |
100304 KB |
Execution killed with signal 11 |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
49440 KB |
answer = 4 |
2 |
Correct |
28 ms |
49524 KB |
answer = 1 |
3 |
Correct |
28 ms |
49560 KB |
answer = 2 |
4 |
Correct |
25 ms |
49492 KB |
answer = 1 |
5 |
Correct |
25 ms |
49484 KB |
answer = 2 |
6 |
Correct |
25 ms |
49484 KB |
answer = 1 |
7 |
Correct |
26 ms |
49544 KB |
answer = 1 |
8 |
Correct |
25 ms |
49428 KB |
answer = 3 |
9 |
Correct |
25 ms |
49548 KB |
answer = 2 |
10 |
Correct |
26 ms |
49552 KB |
answer = 3 |
11 |
Correct |
29 ms |
49484 KB |
answer = 2 |
12 |
Correct |
29 ms |
49476 KB |
answer = 3 |
13 |
Correct |
29 ms |
49480 KB |
answer = 2 |
14 |
Correct |
26 ms |
49512 KB |
answer = 1 |
15 |
Correct |
27 ms |
49484 KB |
answer = 1 |
16 |
Correct |
27 ms |
49456 KB |
answer = 1 |
17 |
Correct |
25 ms |
49572 KB |
answer = 1 |
18 |
Runtime error |
84 ms |
100304 KB |
Execution killed with signal 11 |
19 |
Halted |
0 ms |
0 KB |
- |