| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 818480 | pavement | Longest beautiful sequence (IZhO17_subsequence) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bitseq.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> bitseq(vector<int> a, vector<int> c) {
const int k = 10;
int n = a.size(), cl[1 << k][1 << k][k + 1];
vector<int> dp(n, 1), prv(n, -1);
memset(cl, -1, sizeof cl);
for (int i = 0; i < n; i++) {
for (int lh = 0; lh < (1 << k); lh++) {
int rh = a[i] >> k;
int lh_i = a[i] & ((1 << k) - 1);
if (c[i] < __builtin_popcount(lh & lh_i) || c[i] - __builtin_popcount(lh & lh_i) > k) {
continue;
}
int to = cl[lh][rh][c[i] - __builtin_popcount(lh & lh_i)];
if (to != -1) {
if (dp[to] + 1 > dp[i]) {
dp[i] = dp[to] + 1;
prv[i] = to;
}
}
}
for (int rh = 0; rh < (1 << k); rh++) {
int lh = a[i] & ((1 << k) - 1);
int rh_i = (a[i] ^ lh) >> k;
if (cl[lh][rh][__builtin_popcount(rh & rh_i)] == -1 || dp[cl[lh][rh][__builtin_popcount(rh & rh_i)]] < dp[i]) {
cl[lh][rh][__builtin_popcount(rh & rh_i)] = i;
}
}
}
int mx = -1;
for (int i = 0; i < n; i++) {
if (mx == -1 || dp[i] >= dp[mx]) {
mx = i;
}
}
vector<int> ret;
while (mx != -1) {
ret.push_back(mx + 1);
mx = prv[mx];
}
reverse(ret.begin(), ret.end());
return ret;
}