| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 475178 | TheScrasse | Longest beautiful sequence (IZhO17_subsequence) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<
#define INF (int)1e9
#define mod 998244353
#define maxn 100010
#define maxb 1024
#defina maxs 1048576
#define maxp 11
int i, i1, j, k, k1, t, n, m, flag[10], a[maxn], b[maxn];
int mk1, mk2, mk3, cr, pr[maxn], pc[maxs];
array<int, 2> dp[maxb][maxb][maxp], res;
array<int, 5> rs;
vector<int> rsv;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
#if !ONLINE_JUDGE && !EVAL
ifstream cin("input.txt");
ofstream cout("output.txt");
#endif
for (i = 0; i < maxs; i++) pc[i] = __builtin_popcount(i);
cin >> n;
for (i = 1; i <= n; i++) {
cin >> a[i];
}
for (i = 1; i <= n; i++) {
cin >> b[i];
}
for (i = 1; i <= n; i++) {
mk1 = (a[i] >> 10); mk2 = a[i] - (1 << 10) * mk1;
// cout << "mk1, mk2 = " << mk1 _ mk2 << nl;
rs = {1, 0, 0, 0, 0};
for (mk3 = 0; mk3 < (1 << 10); mk3++) {
m = b[i] - pc[mk1 & mk3];
if (m < 0 || m > 10) continue;
rs = max(rs, {dp[mk3][mk2][m][0] + 1, dp[mk3][mk2][m][1], mk3, mk2, m});
// cout << "query" _ mk3 _ mk2 _ m _ dp[mk3][mk2][m][0] + 1 << nl;
}
res = max(res, {rs[0], i}); pr[i] = rs[1];
for (mk3 = 0; mk3 < (1 << 10); mk3++) {
m = pc[mk2 & mk3];
if (rs[0] > dp[mk1][mk3][m][0]) {
dp[mk1][mk3][m] = {rs[0], i};
}
// cout << "upd" _ mk1 _ mk3 _ m _ dp[mk1][mk3][m][0] << nl;
}
}
/* for (i = 1; i <= n; i++) cout << pr[i] << ' ';
cout << nl; */
cout << res[0] << nl;
cr = res[1];
while (cr != 0) {
rsv.pb(cr); cr = pr[cr];
}
reverse(rsv.begin(), rsv.end());
for (auto u : rsv) cout << u << ' ';
cout << nl;
return 0;
}