Submission #85690

#	Time	Username	Problem	Language	Result	Execution time	Memory
85690		farukkastamonuda	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	6045 ms	99688 KiB

subsequence

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fi first
#define se second
#define mp make_pair
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define pb push_back
#define li 100005
using namespace std;
int n,A[li],B[li],now[li],pr[li];
int half=10;
pair<int,int> dp[(1<<10)+150][(1<<10)+150][11];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&A[i]);
	for(int i=1;i<=n;i++) scanf("%d",&B[i]);
	int res=-1,res_p=-1;
	for(int i=1;i<=n;i++){
		now[i]=1;
		int j=0,origin=(A[i]>>half),firsthalf=(A[i]>>half);
		for(int mask=0;mask<(1<<half);mask++){
			int left=B[i]-__builtin_popcount(origin&mask);
			if(left>=0 && left<=10){
				int lasthalf=(A[i]&((1<<half)-1));
				if(dp[mask][lasthalf][left].fi+1>now[i]){
					now[i]=dp[mask][lasthalf][left].fi+1;
					j=dp[mask][lasthalf][left].se;
				}
			}
		}
		pr[i]=j;
		for(int mask=0;mask<(1<<half);mask++){
			int changed=__builtin_popcount(A[i]&mask);
			if(dp[firsthalf][mask][changed].fi<now[i]){
				dp[firsthalf][mask][changed]={now[i],i};
			}
		}
		if(now[i]>res){
			res=now[i];
			res_p=i;
		}
	}
	printf("%d\n",res);
	vector<int> v;
	while(res_p>0){
		v.pb(res_p);
		res_p=pr[res_p];
	}
	for(int i=(int)v.size()-1;i>=0;i--) printf("%d ",v[i]);
	return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
subsequence.cpp:17:29: 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:18:29: 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",&B[i]);
                        ~~~~~^~~~~~~~~~~~

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