Submission #527795

#	Time	Username	Problem	Language	Result	Execution time	Memory
527795		rsjw	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	1964 ms	92996 KiB

subsequence

#include <cstdio>
#include <algorithm>
#include <vector>
const int maxcount = 10;
const int mask = 1 << maxcount;
const int maxn = 100005;
using namespace std;
int cnt[mask];
int a[maxn],k[maxn];
int f[mask][mask][maxcount+1],id[mask][mask][maxcount+1];
int last[maxn];
int n;
vector<int> sol;
int main() {
	//freopen("1.in","r",stdin);
	scanf("%d",&n);
	for(int i=1; i<mask; i++) cnt[i]=cnt[i>>1]+(i&1);
	for(int i=1; i<=n; i++) scanf("%d",&a[i]);
	for(int i=1; i<=n; i++) scanf("%d",&k[i]);
	int ans,cur0,cur1,bc;
	int maxid,maxn=0;
	for(int i=1; i<=n; i++) {
		cur0=(a[i])>>maxcount,cur1=(a[i])&(mask-1);
		ans=1;
		for(int pre1=0;pre1<mask;pre1++) {
			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++) {
			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 x=maxid;
	while(x) sol.push_back(x),x=last[x];
	//assert(maxn==sol.size());
	sort(sol.begin(),sol.end());
	printf("%d\n",(int)maxn);
	for(auto i:sol) {
		printf("%d ",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]
   16 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
subsequence.cpp:18:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  for(int i=1; i<=n; i++) scanf("%d",&a[i]);
      |                          ~~~~~^~~~~~~~~~~~
subsequence.cpp:19:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  for(int i=1; i<=n; i++) scanf("%d",&k[i]);
      |                          ~~~~~^~~~~~~~~~~~
subsequence.cpp:38:6: warning: 'maxid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |  int x=maxid;
      |      ^

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