Submission #147170

#	Time	Username	Problem	Language	Result	Execution time	Memory
147170		abacaba	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5696 ms	89504 KiB

subsequence

#include <stdio.h>
#include <algorithm>
using namespace std;

const int N = 1e5 + 1;
const int M = 1 << 10;
const int K = 21;
int n, a[N], k[N], dp[N], f[M][M][K], back[N];

void rec(int i) {
	if(i) {
		rec(back[i]);
		printf("%d ", i);
	}
}

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", &k[i]);
	for(int i = 1; i <= n; ++i) {
		dp[i] = 1;
		int bit = (i & 1), second_half = 0, first_half = 0;
		for(int j = 0; j < 10; ++j) {
			if((1024 << j) & a[i])
				second_half |= (1 << j);
			if((1 << j) & a[i])
				first_half |= (1 << j);
		}
		for(int mask = 0; mask < M; ++mask) {
			int k2 = k[i] - __builtin_popcount(mask & first_half);
			if(k2 >= 0 && dp[f[mask][second_half][k2]] + 1 > dp[i])
				dp[i] = dp[f[mask][second_half][k2]] + 1,
				back[i] = f[mask][second_half][k2];
		}
		for(int mask = 0; mask < M; ++mask) {
			int k1 = __builtin_popcount(mask & second_half);
			if(dp[i] > dp[f[first_half][mask][k1]])
				f[first_half][mask][k1] = i;
		}
	}
	int ans = max_element(dp + 1, dp + 1 + n) - dp;
	printf("%d\n", dp[ans]);
	rec(ans);
	return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:25:7: warning: unused variable 'bit' [-Wunused-variable]
   int bit = (i & 1), second_half = 0, first_half = 0;
       ^~~
subsequence.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
subsequence.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
subsequence.cpp:22: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: 60 / 60