이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
// cout << n << endl;
int a[n + 1];
int k[n + 1];
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
for(int i = 1; i <= n; ++i) {
cin >> k[i];
}
int dp[n + 1];
int from[n + 1];
int store [1024][1024][11];
// best index if we have a mask for the first 10 bits and a mask for the second 10 bits and we need i setbits in the first 10
for(int i = 1; i <= n; ++i) {
int lmask = a[i] >> 10; // top mask
int rmask = a[i] & 1023; // bottom mask
int best = 0;
for(int m = 0; m < 1024; ++m) {
int numset = __builtin_popcount(m & rmask);
int need = k[i] - numset;
if(need > 10 || need < 0) {
continue;
}
if(dp[best] < dp[store[lmask][m][need]]) {
best = store[lmask][m][need];
}
}
dp[i] = 1 + dp[best];
from[i] = best;
for(int m = 0; m < 1024; ++m) {
int numset =__builtin_popcount(m & lmask);
if(dp[store[m][rmask][numset]] < dp[i]) {
store[m][rmask][numset] = i;
}
}
}
int highest = 1;
for(int i = 1; i <= n; ++i) {
if(dp[highest] < dp[i]) {
highest = i;
}
}
vector<int> answer;
while(highest) {
answer.push_back(highest);
highest = from[highest];
}
reverse(answer.begin(), answer.end());
cout << answer.size() << endl;
for(int i = 0; i < (int)answer.size(); ++i) {
cout << answer[i] << " ";
}
cout << endl;
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... |