Submission #901692

#	Time	Username	Problem	Language	Result	Execution time	Memory
901692		OAleksa	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3661 ms	193644 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 1e5 + 69;
const int K = 11;
const int M = (1 << 10);
int n, a[N], k[N], par[N], sk[N];
pair<int, int> dp[M][M][K];
int b[M][M];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
	  cin >> n;
	  for (int i = 0;i < M;i++) {
	  	for (int j = 0;j < M;j++)
	  		b[i][j] = __builtin_popcount(i & j);
	  }
	  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++) {
			int bst = 0, pr = 0;
			for (int j = 0;j < M;j++) {
				int x = b[a[i] & (M - 1)][j];
				if (k[i] < x || k[i] - x > 10)
					continue;
				if (dp[j][a[i] >> 10][k[i] - x].f >= bst) {
					bst = dp[j][a[i] >> 10][k[i] - x].f;
					pr = dp[j][a[i] >> 10][k[i] - x].s;
				}
			}
			par[i] = pr;
			sk[i] = bst + 1;
			for (int j = 0;j < M;j++) {
				int nj = b[j][a[i] >> 10];
				if (sk[i] > dp[a[i] & (M - 1)][j][nj].f) {
					dp[a[i] & (M - 1)][j][nj].f = sk[i];
					dp[a[i] & (M - 1)][j][nj].s = i;
				}
			}
		}
		int mx = 1;
		for (int i = 2;i <= n;i++) {
			if (sk[i] > sk[mx]) 
				mx = i;
		}
		int t = mx;
		vector<int> ans;
		while (t != 0) {
			ans.push_back(t);
			t = par[t];
		}
		reverse(ans.begin(), ans.end());
		cout << ans.size() << '\n';
		for (auto i : ans)
			cout << i << " ";
	}
  return 0;
}

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