Submission #93040

#	Time	Username	Problem	Language	Result	Execution time	Memory
93040		Vardanyan	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	15 ms	1016 KiB

subsequence

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1000 * 100 + 5;
const int M = (1 << 11);
int dp[M][13][M];
int dp_pos[M][13][M];
int a[N];
int K[N];
int par[N];
int cnt[N];
int CNT(int n){
	if(cnt[n]) return cnt[n];
	int ans = 0;
	for (int i = 0; i < 12; i++) if ((n >> i) & 1) ans++;
	return cnt[n] =  ans;
}
int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> K[i];
	int lst = 1;
	int ans = 0;
	for (int i = 1; i <= n; i++){
		int u = a[i] >> 10;
		int l = a[i]%1024;
		int w = 0;
		int w_p = 0;
		for (int mask = 0; mask < M; mask++){
			int bt = CNT(u&mask);
			int need = K[i] - bt;
			int now = dp[mask][need][l];
			now++;
			if (now > w){
				w = now;
				w_p = dp_pos[mask][need][l];
				if (w > ans){
					ans = w;
					lst = i;
				}
			}
		}
		par[i] = w_p;
		for (int mask = 0; mask < M; mask++){
			int q = CNT(l&mask);
			if (dp[u][q][mask] < w){
				dp[u][q][mask] = w;
				dp_pos[u][q][mask] = i;
			}
		}
	}
	vector<int> all;
	all.push_back(lst);
	while (par[lst]){
		lst = par[lst];
		all.push_back(lst);
	}
	reverse(all.begin(), all.end());
	cout << ans << endl;
	for (int i = 0; i < all.size(); i++){
		cout << all[i] << endl;
	}
	return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < all.size(); i++){
                  ~~^~~~~~~~~~~~

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