Submission #340998

#	Time	Username	Problem	Language	Result	Execution time	Memory
340998		GioChkhaidze	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	5158 ms	56812 KiB

subsequence

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

const int N = 1e5 + 5;

int n, i, a[N], k[N], res[N], l[N];
int dp[1121][1121][12];

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (i = 1; i <= n; ++i) 
		cin >> a[i];
	
	for (i = 1; i <= n; ++i) 
		cin >> k[i];
	
	int ans = 0, id, maskl, maskr, mask, idx, nk, b, x, y;
	for (i = 1; i <= n; ++i) {
		x = a[i], y = k[i];
	
		maskl = maskr = 0;
		for (b = 0; b < 10; ++b) {
			maskl |= (x & (1 << b));
			maskr |= ((x >> 10) & (1 << b));
		}
		
		res[i] = 1;
		for (mask = 0; mask < 1024; ++mask) {
			nk = __builtin_popcount((maskl & mask));
			if (nk > y) continue;
			if (y - nk > 10) continue;
			idx = dp[mask][maskr][y - nk];
			if (res[i] < res[idx] + 1) 
				res[i] = res[idx] + 1, l[i] = idx;
		}

		for (mask = 0; mask < 1024; ++mask) {
			nk = __builtin_popcount((maskr & mask));
			idx = dp[maskl][mask][nk];
			if (res[idx] < res[i]) 
				dp[maskl][mask][nk] = i;
		}
		
		if (ans < res[i]) ans = res[i], id = i;	
	}
	
	cout << ans << "\n";
	vector < int > ns;
	while (id) {
		ns.push_back(id);
		id = l[id];
	}
	
	for (int i = ns.size() - 1; i >= 0; --i)
		cout << ns[i] << " ";
}

Compilation message (stderr)

subsequence.cpp:9:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 | main () {
      |       ^

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