Submission #89677

#	Time	Username	Problem	Language	Result	Execution time	Memory
89677		antimirage	Longest beautiful sequence (IZhO17_subsequence)	C++11	40 / 100	6031 ms	55652 KiB

subsequence

#include <bits/stdc++.h>
 
#define fr first
#define sc second
#define mk make_pair
#define pb emplace_back
#define all(s) s.begin(), s.end()
 
using namespace std;
 
const int N = 1e5 + 5;
 
int dp[25][1025][1025], p[N], n, ar[N], k[N], ans, ind[25][1025][1025], last, path[N], sz, cn[N];
 
main()
{
	for (int j = 0; j < 1024; j++)
		cn[j] = __builtin_popcount(j);
		
	cin >> n;
	
	for (int i = 1; i <= n; i++)
		scanf("%d", &ar[i]);
		
	for (int i = 1; i <= n; i++)
		scanf("%d", &k[i]);
		
	for (int i = 1; i <= n; i++)
	{
		int pref = (ar[i] >> 10), suf = ar[i] % 1024, res = 0;
		
		for (int j = 0; j < 1024; j++)
		{
			if ( cn[ j & suf ] > k[i] ) continue;
			
			if ( dp[ k[i] - cn[ j & suf ] ][pref][j] > res )
			{
				res = dp[ k[i] - cn[ j & suf ] ][pref][j];
				p[i] = ind[ k[i] - cn[ j & suf ] ][pref][j];
			}
		}
		res++;
		
		if (res > ans){
			ans = res;
			last = i;
		}
		
		for (int j = 0; j < 1024; j++){
			if (res > dp[cn[pref & j] ][j][suf])
			{
				dp[cn[pref & j] ][j][suf] = res;
				ind[cn[pref & j] ][j][suf] = i;
			}
		}
	}
	cout << ans << endl;
	
	while (ans--){
		path[++sz] = last;
		last = p[last];
	}
	for (int i = sz; i >= 1; i--)
		printf("%d ", path[i]);
}

Compilation message (stderr)

subsequence.cpp:15:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &ar[i]);
   ~~~~~^~~~~~~~~~~~~~
subsequence.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k[i]);
   ~~~~~^~~~~~~~~~~~~

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