Submission #167918

#	Time	Username	Problem	Language	Result	Execution time	Memory
167918		mosiashvililuka	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	5062 ms	56520 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,f[100009],g[100009],dp[100009],nxt[100009],k[(1<<11)][(1<<11)][12],zx,xc,i,j,pas,pas2,cv,qw,we,jk;
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	qw=(1<<10);we=(1<<20);
	cin>>a;
	for(c=1; c<=a; c++) cin>>f[c];
	for(c=1; c<=a; c++) cin>>g[c];
	for(c=10; c<20; c++) xc+=(1<<c);
	for(c=0; c<10; c++) zx+=(1<<c);
	for(c=a; c>=1; c--){
		d=(f[c]&zx);
		e=(f[c]&xc);
      j=e/qw;
		for(i=0; i<(1<<10); i++){
//		    cout<<dp[c]<<" "<<dp[k[i][e][__builtin_popcount((i&d))]+1]<<endl;
//if(i==2) cout<<__builtin_popcount((i^d))<<" vfds "<<endl;
          jk=__builtin_popcount((i&d));
			if(dp[c]<dp[k[i][j][jk]]+1){
/*			    if(c==1){
			        cout<<k[i][e][__builtin_popcount((i&d))]<<" "<<i<<" "<<e<<endl;
			    }*/
				nxt[c]=k[i][j][jk];
				dp[c]=dp[k[i][j][jk]]+1;
				if(pas<dp[c]){
					pas=dp[c];
					pas2=c;
				}
			}
		}
      j=-1;
		for(i=0; i<we; i+=qw){
		    j++;
			cv=__builtin_popcount((i&e));
			if(cv>g[c]||g[c]-cv>10) continue;
          jk=g[c]-cv;
			if(dp[k[d][j][jk]]<dp[c]){
//			    cout<<d<<" zx "<<i<<endl;
//			    if(d==16) cout<<i<<" d "<<dp[c]<<endl;
				k[d][j][jk]=c;
/*				if(k[16][0][0]==2){
				    cout<<d<<" "<<i<<" "<<g[c]-cv<<endl;
				}*/
			}
		}
//		cout<<k[16][0][0]<<endl;
//cout<<k[2][65536/(1<<10)][1]<<endl;
	}
	cout<<pas<<endl;
	c=pas2;
	while(c!=0){
		cout<<c<<" ";
		c=nxt[c];
	}
	return 0;
}

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