This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif
const int M = 1 << 10;
const int N = 1e5 + 5;
int a[N], k[N];
int dp[N], pre[N];
int best[M][M][10], id[M][M][10];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= n; ++i) {
cin >> k[i];
}
for (int i = 1; i <= n; ++i) {
for (int x = 0; x < M; ++x) {//fix first 10 bits.
int t = k[i] - __builtin_popcount(a[i] & x);
if (t < 0) continue;
int suf = a[i] >> 10;
if (best[x][suf][t] >= dp[i]) {
dp[i] = best[x][suf][t] + 1;
pre[i] = id[x][suf][t];
}
}
for (int suf = 0; suf < M; ++suf) {
int pref = a[i] & (M - 1);
int cnt = __builtin_popcount((a[i] >> 10) & suf);
if (dp[i] > best[pref][suf][cnt]) {
id[pref][suf][cnt] = i;
best[pref][suf][cnt] = dp[i];
}
}
}
int ind = max_element(dp + 1, dp + 1 + n) - dp;
vector<int> seq;
while (ind) {
seq.push_back(ind);
ind = pre[ind];
}
reverse(seq.begin(), seq.end());
cout << seq.size() << '\n';
for (int i : seq) {
cout << i << ' ';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |