Submission #590833

#	Time	Username	Problem	Language	Result	Execution time	Memory
590833		Mazaalai	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4342 ms	92012 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 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];
}

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