Submission #527799

#	Time	Username	Problem	Language	Result	Execution time	Memory
527799		rsjw	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	1989 ms	92100 KiB

subsequence

#include <vector>
#include <iostream>

const int maxcount = 10;
const int mask = 1 << maxcount;
const int maxn = 100005;

using namespace std;
int cnt[mask];//popcount array

int f[mask][mask][maxcount+1];

int last[maxn],id[mask][mask][maxcount+1];//store position of last chosen element

int a[maxn],k[maxn];
int n;

int sol[maxn],len;//generate path

int main() {
	//freopen("1.in","r",stdin);
	cin>>n;
	for(int i=1; i<mask; i++) {
		cnt[i]=cnt[i>>1]+(i&1);
	}
	for(int i=1; i<=n; i++) {
		cin>>a[i];
	}
	for(int i=1; i<=n; i++) {
		cin>>k[i];
	}
	int maxid,maxn=0;
	for(int i=1; i<=n; i++) {
		int cur0=(a[i])>>maxcount,cur1=(a[i])&(mask-1),ans=1;
		for(int pre1=0; pre1<mask; pre1++) {
			int bc=k[i]-cnt[pre1&cur1];
			if(bc>=0 && bc<=maxcount && ans<f[pre1][cur0][bc]+1) {
				ans=f[pre1][cur0][bc]+1,last[i]=id[pre1][cur0][bc];
			}
		}
		for(int nex0=0; nex0<mask; nex0++) {
			int bc=cnt[nex0&cur0];
			if(ans>f[cur1][nex0][bc]) {
				f[cur1][nex0][bc]=ans,id[cur1][nex0][bc]=i;
			} 
		}
		if(maxn<ans) {
			maxn=ans;
			maxid=i;
		}
	}
	int cur=maxid;
	while(cur) {
		sol[++len]=cur;
		cur=last[cur];
	}
	cout<<len<<endl;
	for(int i=len;i>=1;i--) {
		if(i==1) {
			cout<<sol[i]<<endl;
		}else{
			cout<<sol[i]<<" ";
		} 
	}
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:55:6: warning: 'maxid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |   cur=last[cur];
      |   ~~~^~~~~~~~~~

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