Submission #224785

#	Time	Username	Problem	Language	Result	Execution time	Memory
224785		Abelyan	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2891 ms	61324 KiB

subsequence

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;

const int N = 1e5 + 6,MSK=1030;
int a[N],k[N];
int dp[MSK][22][MSK], cnt[MSK], mx[N], nax[N],ind[MSK][22][MSK];

int count(int k){
	int ans = 0;
	for (int i = 0; i < 10; i++){
		if ((1 << i)&k)ans++;
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i < 1024; i++){
		cnt[i] = count(i);
	}
	for (int i = 0; i < n; i++){
		cin >> a[i];
		nax[i] = -1;
	}
	//assert(n == 4 && a[0] == 1 && a[1] == 2 && a[2] == 3 && a[3] == 4);
	int ans=0, ansind;
	for (int i = 0; i < n; i++){
		cin >> k[i];
		int fr = a[i] / 1024;
		int sc = a[i] % 1024;
		mx[i] = 1;
		for (int ms = 0; ms < 1024; ms++){
			//mx[i] = max(mx[i], dp[fr][k[i] - cnt[sc&ms]][ms]);
			if (k[i]<cnt[sc&ms])continue;
			int arj=dp[fr][k[i] - cnt[sc&ms]][ms];
			//cout<<dp[fr][k[i] - cnt[sc&ms]][ms]<<endl;
			if (mx[i] < arj+1){
				nax[i] = ind[fr][k[i] - cnt[sc&ms]][ms];
				mx[i] = arj+1;
			}
		}
		for (int ms = 0; ms < 1024; ms++){
			if (mx[i]>dp[ms][cnt[ms&fr]][sc]){
				ind[ms][cnt[ms&fr]][sc] = i;
				dp[ms][cnt[ms&fr]][sc] = mx[i];
			}
		}
		//cout<<mx[i]<<endl;
		if (mx[i] > ans){
			ans = mx[i];
			ansind = i;
		}
	}

	//assert(ans == 4);
	cout << ans<< endl;
	int tv = ansind;
	vector<int> v;
	while (tv != -1){
		v.push_back(tv + 1);
		tv = nax[tv];
	}
	reverse(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++){
		if (i == v.size() - 1){
			cout << v[i];
		}
		else cout << v[i] << " ";
	}
	cout << endl;
	return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++){
                  ~~^~~~~~~~~~
subsequence.cpp:70:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i == v.size() - 1){
       ~~^~~~~~~~~~~~~~~
subsequence.cpp:65:18: warning: 'ansind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   v.push_back(tv + 1);
               ~~~^~~

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