Submission #89664

#	Time	Username	Problem	Language	Result	Execution time	Memory
89664		antimirage	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	6084 ms	69196 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;

vector <int> path;

main()
{
	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 ( __builtin_popcount( j & suf ) > k[i] ) continue;
			
			if ( dp[ k[i] - __builtin_popcount( j & suf ) ][pref][j] > res )
			{
				res = dp[ k[i] - __builtin_popcount( j & suf ) ][pref][j];
				p[i] = ind[ k[i] - __builtin_popcount( j & suf ) ][pref][j];
			}
		}
		res++;
		
		if (res > ans){
			ans = res;
			last = i;
		}
		
		for (int j = 0; j < 1024; j++){
			if (res > dp[__builtin_popcount(pref & j) ][j][suf])
			{
				dp[__builtin_popcount(pref & j) ][j][suf] = res;
				ind[__builtin_popcount(pref & j) ][j][suf] = i;
			}
		}
	}
	cout << ans << endl;
	
	while (last){
		path.push_back( last );
		last = p[last];
	}
	reverse(all(path));
	
	for (auto it : path)
		printf("%d ", it);
}
/**
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:17:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &ar[i]);
   ~~~~~^~~~~~~~~~~~~~
subsequence.cpp:25: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