Submission #993774

#	Time	Username	Problem	Language	Result	Execution time	Memory
993774		duckindog	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3021 ms	93524 KiB

subsequence

#include<bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
int n;
int a[N], k[N];

pair<int, int> f[1 << 10][1 << 10][11];
int dp[N], trace[N];

int main(){
	cin.tie(0)->sync_with_stdio(0);

	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= n; ++i) cin >> k[i];

	for (int i = 1; i <= n; ++i) { 
		auto& ret = dp[i]; ret = 1;
		
		int pref = (a[i] & (1 << 10) - 1), suff = (a[i] >> 10);
		for (int mask = 0; mask < (1 << 10); ++mask) { 
			int cnt = k[i] - __builtin_popcount(pref & mask);
			if (0 <= cnt && cnt < 10 && ret < f[mask][suff][cnt].first + 1) { 
				ret = f[mask][suff][cnt].first + 1;
				trace[i] = f[mask][suff][cnt].second;
			}
		}
		for (int mask = 0; mask < (1 << 10); ++mask) { 
			int cnt = __builtin_popcount(mask & suff);
			if (f[pref][mask][cnt].first < ret) f[pref][mask][cnt] = {ret, i};
		}
	}

	int it = 0;
	for (int i = 1; i <= n; ++i) if (dp[it] < dp[i]) it = i;

	vector<int> answer;
	while (it) { 
		answer.push_back(it);
		it = trace[it];
	}
	
	cout << answer.size() << "\n";
	for (const auto& x : vector<int>(answer.rbegin(), answer.rend())) cout << x << " ";
	cout << "\n";
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:22:32: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   22 |   int pref = (a[i] & (1 << 10) - 1), suff = (a[i] >> 10);
      |                      ~~~~~~~~~~^~~

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