제출 #901688

#제출 시각아이디문제언어결과실행 시간메모리
901688OAleksaLongest beautiful sequence (IZhO17_subsequence)C++14
40 / 100
6080 ms184592 KiB
#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];
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 = 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 = __builtin_popcount(a[i] & 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 = __builtin_popcount((j << 10) & a[i]);
				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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...