이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#pragma GCC target("popcnt")
using namespace std;
int b[21][1<<10][1<<10], bindex[21][1<<10][1<<10];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n; cin >> n;
int a[n], k[n];
for (int& x : a) cin >> x;
for (int& x : k) cin >> x;
int bitcnt[1<<20];
for (int i = 0; i < 1 << 20; i++) {
bitcnt[i] = __builtin_popcount(i);
}
int dp[n];
int pre[n];
for (int i = 0; i < n; i++) {
dp[i] = 1;
pre[i] = i;
int U = a[i] >> 10, L = a[i] & 1023;
for (int x = 0; x < 1 << 10; x++) {
if (k[i] - bitcnt[x & L] < 0) continue;
if (b[k[i] - bitcnt[x & L]][U][x] + 1 > dp[i]) {
dp[i] = b[k[i] - bitcnt[x & L]][U][x] + 1;
pre[i] = bindex[k[i] - bitcnt[x & L]][U][x];
}
}
for (int x = 0; x < 1 << 10; x++) {
if (dp[i] > b[bitcnt[U & x]][x][L]) {
b[bitcnt[U & x]][x][L] = dp[i];
bindex[bitcnt[U & x]][x][L] = i;
}
}
}
int final = max_element(dp, dp+n) - dp;
vector<int> subs;
while (final != pre[final]) {
subs.push_back(final);
final = pre[final];
}
subs.push_back(final);
reverse(subs.begin(), subs.end());
cout << subs.size() << "\n";
for (int x : subs) cout << x+1 << " ";
}
# | 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... |