Submission #590828

#	Time	Username	Problem	Language	Result	Execution time	Memory
590828		Mazaalai	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2162 ms	101980 KiB

subsequence

#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 bitCnt[M][N];
int par[N];
PII dp[M][M][11]; // len, pos
signed main() {

    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    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;
    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 = 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++) {
    		int &cur = bitCnt[rhs][j];
    		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];
}

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