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 <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1'000'02;
int k[N], a[N], dp[N], hrashqiverj[N], p[N], hrashq[258];
int main(){
int n;
cin >> n;
bool ok = true;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (a[i] >= 256) ok = false;
}
for (int i = 0; i < n; i++)
cin >> k[i];
if (!ok){
for (int i = 0; i < n; i++) {
dp[i] = 1;
p[i] = i;
for(int j = 0; j < i; j++) {
int tmp = (a[j] & a[i]);
if (__builtin_popcount(tmp) == k[i]) {
if(dp[i] < dp[j] + 1){
dp[i] = dp[j] + 1;
p[i] = j;
}
}
}
}
}
else {
for(int i = 0; i < n; i++) {
dp[i] = 1;
p[i] = i;
for(int j = 0; j < 256; j++) {
int tmp = a[i] & j;
if(__builtin_popcount(tmp) == k[i]) {
if(dp[i] < hrashq[j] + 1) {
dp[i] = hrashq[j] + 1;
p[i] = hrashqiverj[j];
}
}
}
//cerr << dp[i] << ' ';
if(hrashq[a[i]] < dp[i]) {
hrashq[a[i]] = max(hrashq[a[i]], dp[i]);
hrashqiverj[a[i]] = i;
}
}
}
vector<int> ban;
int ind = max_element(dp, dp + n) - dp;
cout << dp[ind] << '\n';
while(p[ind] != ind){
ban.push_back(a[ind]);
ind = p[ind];
}
ban.push_back(a[ind]);
reverse(ban.begin(), ban.end());
for(int a: ban) {
cout << a << ' ';
}
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... |