Submission #92730

#	Time	Username	Problem	Language	Result	Execution time	Memory
92730		GioChkhaidze	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	6012 ms	1912 KiB

subsequence

#include <bits/stdc++.h>

#define F first
#define S second
#define Pb push_back

using namespace std;

int n,a[100005],k[100005],X,Ans;

pair < int , int > Dp[100005],Mx;

vector < int > ANS;

main ()
{
	cin>>n;
	
	for (int i=1; i<=n; i++)
		cin>>a[i];
	
	for (int i=1; i<=n; i++)
	{
		cin>>k[i];
		Dp[i].F=1;
	}
	
	for (int i=1; i<=n; i++)
	{
		Mx.F=0;
		Mx.S=0;
		
		for (int j=i-1; j>=1; j--)
			if (__builtin_popcount(a[j]&a[i])==k[i] && Mx.F<Dp[j].F)
			{
				Mx.F=Dp[j].F;
				Mx.S=j;
			}
			
		Dp[i].F=Mx.F+1;
		Dp[i].S=Mx.S;
		
		Ans=max(Ans,Dp[i].F);
	}
	
	cout<<Ans<<endl;
	
	for (int i=n; i>=1; i--)
		if (Ans==Dp[i].F) X=i;
				
	while (Dp[X].F!=1)
	{
		ANS.Pb(X);
		X=Dp[X].S;
	}
	
	ANS.Pb(X);
	
	reverse(ANS.begin(),ANS.end());
	
	for (int i=0; i<ANS.size(); i++)
		cout<<ANS[i]<<" ";
}
/*

4
1 2 3 4
10 0 1 0

2
8 9
20 0

5
5 3 5 3 5
10 1 20 1 20

*/

Compilation message (stderr)

subsequence.cpp:15:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:61:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<ANS.size(); i++)
                ~^~~~~~~~~~~

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