이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define log(x) (63^__builtin_clzll(x))
//#define endl '\n'
#define all(x) (x).begin() , (x).end()
pair<int, int> dp[1 << 10][1 << 10][11];
void solve() {
int n;
cin >> n;
vector<int> a(n), k(n);
for(int i = 0; i < n; ++i) cin >> a[i];
for(int i = 0; i < n; ++i) cin >> k[i];
int fullDown = (1 << 10) - 1, fullUp = (1 << 20) - 1 - fullDown, ans = 0, last = 0;
vector<int> prev(n, -1);
for(int i = 0; i < n; ++i) {
int mx = 1, up = ((fullUp & a[i]) >> 10), down = (fullDown & a[i]);
for(int reqUp = 0; reqUp < (1 << 10); ++reqUp) {
int common = __builtin_popcount(reqUp & up);
if(k[i] >= common) {
auto &state = dp[reqUp][down][k[i] - common];
if(state.first + 1 > mx) prev[i] = state.second;
mx = max(mx, state.first + 1);
}
}
if(mx > ans) last = i;
ans = max(ans, mx);
for(int reqDown = 0; reqDown < (1 << 10); ++reqDown) {
int common = __builtin_popcount((reqDown & a[i]));
dp[up][reqDown][common] = max(dp[up][reqDown][common], {mx, i});
}
}
cout << ans << endl;
vector<int> indices;
while(last != -1) {
indices.push_back(last);
last = prev[last];
}
reverse(all(indices));
for(auto j : indices) cout << j + 1 << " ";
cout << endl;
return;
}
main() {
ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr);
int t = 1;
//cin >> t;
while(t--) solve();
return 0;
}
//dp[need][have]
컴파일 시 표준 에러 (stderr) 메시지
subsequence.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
48 | main() {
| ^~~~
# | 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... |