Submission #680936

#	Time	Username	Problem	Language	Result	Execution time	Memory
680936		lev1106	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3827 ms	84596 KiB

subsequence

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

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++) {
		cur = (a[i] & 1023);
		x = cur;
		cur = (a[i] >> 10);
		y = cur;
		mx = 1;
		for (cur = 0; cur < 1024; cur++) {
			x1 = cur;
			kx = k[i] - __popcount(x & x1);
			if (kx < 0 || kx >= 10) continue;
			if (dp[x1][y][kx].first + 1 >= mx) {
				mx = dp[x1][y][kx].first + 1;
				p[i] = dp[x1][y][kx].second;
			}
		}
		for (cur = 0; cur < 1024; cur++) {
			y1 = cur;
			kx = __popcount(y & y1);
			if (kx < 0 || kx >= 10) continue;
			if (mx > dp[x][y1][kx].first) dp[x][y1][kx] = {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.push_back(cur);
		cur = p[cur];
	}
	reverse(ansv.begin(), ansv.end());
	for (int i : ansv) cout << i << " ";
}

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