Submission #590851

#	Time	Username	Problem	Language	Result	Execution time	Memory
590851		Mazaalai	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2307 ms	98568 KiB

subsequence

#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define ALL(x) x.begin(),x.end()
using namespace std;
using PII = pair <int, int>;
using sint = short;
int n, m;
const int N = 1e5+1;
const int M = 1<<10;
PII dp[M][M][11]; 
int nums[N], par[N];
sint bitCnt[M][N], dif[N];
signed main() {
 	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];
    for (int i = 0; i < M; i++) 
    for (int j = i; j < M; j++) 
    	bitCnt[i][j] = bitCnt[j][i] = __builtin_popcount(i&j);
    
    int res = 1, ans = 0, lhs, rhs, tar, x;
    for (int i = 1; i <= n; i++) {
    	lhs = nums[i]>>10;
    	rhs = nums[i]^(lhs<<10);
    	PII tmp = {0, 0}; // len, par
    	for (int j = 0; j < M; j++) {
    		sint &cur = bitCnt[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++) {
    		sint &cur = bitCnt[rhs][j];
    		if (dp[lhs][j][cur].ff < tmp.ff) dp[lhs][j][cur] = tmp;
    	}
    }
    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];
}

• Subtask 1: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 60 / 60