Submission #93057

#	Time	Username	Problem	Language	Result	Execution time	Memory
93057		Vardanyan	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3086 ms	91208 KiB

subsequence

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1000 * 100 + 5;
const int M = 1030;
int dp[M][11][M];
int dp_pos[M][11][M];
int a[N];
int K[N];
int par[N];
int cnt[N];
int CNT(int n){
	int ans = 0;
	for (int i = 0; i < 12; i++) if ((n >> i) & 1) ans++;
	return ans;
}
int main(){
  //  freopen("subsequence.in","r",stdin);
    
  //  freopen("subsequence.out","w",stdout);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) scanf("%d",&a[i]);
	for (int i = 1; i <= n; i++) scanf("%d",&K[i]);
	for(int i = 0;i<=N-1;i++) cnt[i] = CNT(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;
        	if(need>10 || need<0) continue;
			int now = dp[mask][need][l];
			if (now > w){
				w = now;
				w_p = dp_pos[mask][need][l];
			}
		}
		w++;
		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++){
		printf("%d\n",all[i]);
	}
	return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < all.size(); i++){
                  ~~^~~~~~~~~~~~
subsequence.cpp:24:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%d",&a[i]);
                               ~~~~~^~~~~~~~~~~~
subsequence.cpp:25:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%d",&K[i]);
                               ~~~~~^~~~~~~~~~~~

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