제출 #590833

#제출 시각아이디문제언어결과실행 시간메모리
590833MazaalaiLongest beautiful sequence (IZhO17_subsequence)C++17
100 / 100
4342 ms92012 KiB
#include <bits/stdc++.h> #define pb push_back #define ff first #define ss second #define LINE "--------------------\n" #define ALL(x) x.begin(),x.end() using namespace std; using PII = pair <int, int>; int n, m; const int N = 1e5+1; const int M = 1<<10; int nums[N], dif[N]; int par[N]; PII dp[M][M][11]; // len, pos signed main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> nums[i]; for (int i = 1; i <= n; i++) cin >> dif[i]; int res = 1, ans = 0; for (int i = 1; i <= n; i++) { int lhs = nums[i]>>10; int rhs = nums[i]%(1<<10); PII tmp = {0, 0}; // len, par for (int j = 0; j < M; j++) { int cur = __builtin_popcount(lhs&j), tar = dif[i]-cur; if (tar < 0 || tar > 10) continue; if (dp[j][rhs][tar].ff > tmp.ff) tmp = dp[j][rhs][tar]; } tmp.ff++; par[i] = tmp.ss; tmp.ss = i; if (tmp.ff > ans) { res = i; ans = tmp.ff; } for (int j = 0; j < M; j++) { int cur = __builtin_popcount(j&rhs); if (dp[lhs][j][cur].ff < tmp.ff) dp[lhs][j][cur] = tmp; } } int x = ans; while(res > 0) { nums[x--] = res; res = par[res]; } cout << ans << "\n"; for (int i = 1; i <= ans; i++) cout << nums[i] << " \n"[i==ans]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...