Submission #297325

#	Time	Username	Problem	Language	Result	Execution time	Memory
297325		shivensinha4	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4856 ms	175576 KiB

subsequence

#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

const int MXH = (1 << 10) - 1, MXN = 1e5;
int bc[MXH+2], bestVal[MXH+2][MXH+2][21], bestIdx[MXH+2][MXH+2][21], nxt[MXN+1];

int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	for_(i, 0, MXH+1) bc[i] = __builtin_popcount(i);
	int n; cin >> n;
	vi a(n), b(n);
	for_(i, 0, n) cin >> a[n-i-1];
	for_(i, 0, n) cin >> b[n-i-1];
	
	int ans = 0, start = -1;
	for (int i = n-1; i >= 0; i--) {
		int temp = 0, suc = -1;
		int h1 = a[i] >> 10, h2 = a[i] & MXH;
		for_(v, 0, MXH+1) {
			int k = h1 & v;
			if (bc[k] > b[i]) continue;
			if (temp < bestVal[v][h2][b[i]-bc[k]]) {
				temp = bestVal[v][h2][b[i]-bc[k]];
				suc = bestIdx[v][h2][b[i]-bc[k]];
			}
		}
		
		temp += 1;
		nxt[i] = suc;
		
		if (temp > ans) {
			ans = temp;
			start = i;
		}
		
		for_(v, 0, MXH+1) {
			int k = bc[h2 & v];
			if (temp > bestVal[h1][v][k]) {
				bestVal[h1][v][k] = temp;
				bestIdx[h1][v][k] = i;
			}
		}
	}
	
	cout << ans << endl;
	vi seq;
	while (start != -1) {
		seq.push_back(start);
		start = nxt[start];
	}
	
	reverse(seq.begin(), seq.end());
	for (int i: seq) cout << n-i << " ";
	cout << endl;


	return 0;
}

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