제출 #520648

#제출 시각아이디문제언어결과실행 시간메모리
520648CantfindmeLongest beautiful sequence (IZhO17_subsequence)C++17
7 / 100
259 ms163512 KiB
#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][10]; //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 << " ";
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...