Submission #334159

#	Time	Username	Problem	Language	Result	Execution time	Memory
334159		tengiz05	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	5630 ms	48492 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define count __builtin_popcount
#define pb push_back
const int N = 1e5+2;
int a[N], n, m, k[N];
int dp[N];
int par[N];
int f[1024][1024][11];
void solve(int test_case){
	int i, j;
	cin >> n;
	for(i=1;i<=n;i++){
		cin >> a[i];
	}
	for(i=1;i<=n;i++){
		cin >> k[i];
	}
	vector<int> ans;
	for(i=1;i<=n;i++){
		int l = a[i]>>10;
		int r = a[i]&1023;
		int best = 0;
		for(j=0;j<1024;j++){
			int tmp = count(j&r);
			tmp = k[i]-tmp;
			if(tmp < 0 || tmp > 10)continue;
			if(dp[best] < dp[f[l][j][tmp]])best = f[l][j][tmp];
		}
		dp[i] = dp[best]+1;
		par[i] = best;
		for(j=0;j<1024;j++){
			int tmp = count(l&j);
			if(dp[i] > dp[f[j][r][tmp]])f[j][r][tmp] = i;
		}
	}
	m = 1;
	for(i=2;i<=n;i++)if(dp[i] > dp[m])m = i;
	cout << dp[m] << '\n';
	while(m>0){
		ans.pb(m);
		m = par[m];
	}
	reverse(all(ans));
	for(auto x : ans)cout << x << ' ';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int ___T;
	cin >> ___T;
	for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

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