Submission #680937

#	Time	Username	Problem	Language	Result	Execution time	Memory
680937		lev1106	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2587 ms	78996 KiB

subsequence

#include <iostream>
#include <bit>
#include <algorithm>
using namespace std;
int n, i, kx, x, y, x1, yy1, mx, cur, a[100001], p[100001], ansv[100001], ptr;
char k[100001];
pair<int, int> dp[10][1024][1024], ans;

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	#endif
	cin >> n;
	for (i = 1; i <= n; i++) cin >> a[i];
	for (i = 1; i <= n; i++) cin >> cur, k[i] = cur;
	for (i = 1; i <= n; i++) {
		x = (a[i] & 1023);
		y = (a[i] >> 10);
		mx = 1;
		for (x1 = 0; x1 < 1024; x1++) {
			kx = k[i] - __popcount(x & x1);
			if (kx < 0 || kx >= 10) continue;
			if (dp[kx][x1][y].first + 1 >= mx) {
				mx = dp[kx][x1][y].first + 1;
				p[i] = dp[kx][x1][y].second;
			}
		}
		for (yy1 = 0; yy1 < 1024; yy1++) {
			kx = __popcount(y & yy1);
			if (kx < 0 || kx >= 10) continue;
			if (mx > dp[kx][x][yy1].first) dp[kx][x][yy1] = {mx, i};
		}
		if (mx > ans.first) ans = {mx, i};
		//cout << x << " " << y << " " << p[i] << "\n";
	}
	cout << ans.first << "\n";
	cur = ans.second;
	while (cur > 0) {
		ansv[ptr++] = cur;
		cur = p[cur];
	}
	for (i = ptr - 1; i >= 0; i--) cout << ansv[i] << " ";
}

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