Submission #343667

#	Time	Username	Problem	Language	Result	Execution time	Memory
343667		Gurban	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3545 ms	93868 KiB

subsequence

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

using ll = long long;

const int maxn=1e5+5;
const int B = (1<<10);
int n,k[maxn],a[maxn],p[B],pos;
pair<int,int>dp[maxn],jog[B][B][11];
vector<int>v;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	for(int i = 0;i < B;i++) p[i] = __builtin_popcount(i);

	memset(jog,-1,sizeof(jog));

	cin >> n;
	for(int i = 1;i <= n;i++) cin >> a[i];
	for(int i = 1;i <= n;i++) cin >> k[i];
	
	for(int i = 1;i <= n;i++){
		int lf = (a[i]>>10);
		int rg = a[i] - (lf<<10);
		
		dp[i] = {1,-1};

		for(int j = 0;j < B;j++){
			int lp = p[j & lf];
			if(lp <= k[i] and lp+10 >= k[i] and jog[j][rg][k[i]-lp].first + 1 > dp[i].first){
				dp[i] = jog[j][rg][k[i]-lp];
				dp[i].first++;
			}
		}

		if(dp[pos].first < dp[i].first) pos = i;
		
		for(int j = 0;j < B;j++){
			int lp = p[rg & j];
			if(jog[lf][j][lp].first < dp[i].first) jog[lf][j][lp] = {dp[i].first,i};
		}
	}

	cout<<dp[pos].first<<'\n';
	while(pos != -1){
		v.push_back(pos);
		pos = dp[pos].second;
	}
	reverse(v.begin(),v.end());
	for(auto i : v) cout<<i<<' ';
}
/*
4
1 2 3 4
10 0 1 0

2
8 9
20 0

5
5 3 5 3 5
10 1 20 1 20
*/

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