Submission #340468

#	Time	Username	Problem	Language	Result	Execution time	Memory
340468		Tosic	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5791 ms	48444 KiB

subsequence

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;

int n, ans, a[maxn], k[maxn], dp[maxn], prI[maxn], bestL[1<<10][1<<10][11];

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> n;
	for(int i = 0; i < n; ++i){
		cin >> a[i];
	}
	for(int i = 0; i < n; ++i){
		cin >> k[i];
	}
	for(int i = 0; i < n; ++i){
		prI[i] = -1;
	}
	for(int i = 0; i < (1<<10); ++i){
		for(int j = 0; j < (1<<10); ++j){
			for(int x = 0; x < 11; ++x){
				bestL[i][j][x] = -1;
			}
		}
	}
	for(int i = 0; i < n; ++i){
		int rP = a[i]&((1<<10)-1), lP = a[i]/(1<<10);
		int tmpV = 0, prIdx = -1;
		for(int j = 0; j < (1<<10); ++j){
			// bestL ijnum - max of dp for all states that share num bits with section i of ij
			int bitS = k[i]-__builtin_popcount(j&rP);
			if(bitS <0 or bitS > 10){
				continue;
			}
			if(bestL[lP][j][bitS] >=0 and tmpV < dp[bestL[lP][j][bitS]]){
				tmpV = dp[bestL[lP][j][bitS]];
				prIdx = bestL[lP][j][bitS];
			}
		}
		dp[i] = tmpV+1;
		prI[i] = prIdx;
		for(int j = 0; j < (1<<10); ++j){
			int bitS = __builtin_popcount(j&lP);
			if(dp[i] > dp[bestL[j][rP][bitS]]){
				bestL[j][rP][bitS] = i;
			}
		}
	}
	int frI = 0;
	for(int i = 0; i < n; ++i){
		if(dp[i] > ans){
			ans = dp[i];
			frI = i;
		}
	}
	vector<int> res;
	while(frI > -1){
		res.push_back(frI+1);
		frI = prI[frI];
	}
	cout << res.size() << '\n';
	reverse(res.begin(), res.end());
	for(auto tmp:res){
		cout << tmp << ' ';
	}
}

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