Submission #520649

#	Time	Username	Problem	Language	Result	Execution time	Memory
520649		Cantfindme	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	5352 ms	184516 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end() 

const int maxn = 100010;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7; 

int n;
int A[maxn], K[maxn];
pi dp[1<<10][1<<10][11]; //L, all BM, match between BM and R
int trace[maxn];

int32_t main() {
	FAST
	cin >> n;
	for (int i =1;i<=n;i++) cin >> A[i];
	for (int i =1;i<=n;i++) cin >> K[i];

	pi rans = pi(0,0);

	for (int i =1;i<=n;i++) {
		int L = A[i] >> 10;
		int R = A[i] & ((1<<10)-1);
		pi best = pi(0,0);
		
		for (int prevl = 0; prevl < (1 << 10); prevl++) {
			int need = K[i] - __builtin_popcount(prevl & L);
			if (need < 0 or need > 10) continue;
			best = max(best, dp[prevl][R][need]);
		}
		
		best.f += 1;
		trace[i] = best.s;
		rans = max(rans, pi(best.f, i));
		
		for (int bm = 0; bm < (1<<10);bm++) {
			int match = __builtin_popcount(R & bm);
			dp[L][bm][match] = max(dp[L][bm][match], pi(best.f, i));
		}
	}
	
	vector <int> ans;
	int indx = rans.s;
	while (indx != 0) {
		ans.push_back(indx);
		indx = trace[indx];
	}
	
	reverse(all(ans));
	cout << ans.size() << "\n";
	for (auto i: ans) cout << i << " ";
}

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