Submission #968890

#	Time	Username	Problem	Language	Result	Execution time	Memory
968890		starchan	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3579 ms	86332 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int N = 1<<10;
const int LOGM = 21;
const int MX = 1e5+3;

int cnt[N][N];
void pre()
{
	cnt[0][0] = 0;
	for(int i = 0; i < N; i++)
	{
		for(int j = (i == 0); j < N; j++)
			cnt[i][j] = cnt[i/2][j/2]+(i*j)%2;
	}
	return;
}

in ans;
in dp[LOGM][N][N];
int p[MX];

signed main()
{
	fast();
	pre();
	int n;
	cin >> n;
	vector<int> a(n+1);
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	vector<int> k(n+1);
	for(int i = 1; i <= n; i++)
		cin >> k[i];
	for(int i = 1; i <= n; i++)
	{
		in val = {0,0};
		for(int j = 0; j < N; j++)
		{
			int d = cnt[a[i]/N][j];
			if(k[i] >= d)
				val = max(val, dp[k[i]-d][j][a[i]%N]);
		}
		p[i] = val[1]; ans = max(ans, {++val[0], i});
		for(int j = 0; j < N; j++)
			dp[cnt[j][a[i]%N]][a[i]/N][j] = max(dp[cnt[j][a[i]%N]][a[i]/N][j], {val[0], i});
	}
	vector<int> v;
	int x = ans[1];
	while(x)
	{
		v.pb(x);
		x = p[x];
	}
	reverse(v.begin(), v.end());
	cout << v.size() << "\n";
	for(auto x: v)
		cout << x << " ";
	cout << "\n";
	return 0;
}	

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