Submission #314928

#	Time	Username	Problem	Language	Result	Execution time	Memory
314928		dolphingarlic	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5975 ms	92760 KiB

subsequence

#include <bits/stdc++.h>
#define popcnt __builtin_popcount
using namespace std;

const int FM = (1 << 20) - 1, HM = (1 << 10) - 1, N = 1e5 + 1;

int a[N], k[N];
pair<int, int> dp[HM + 1][HM + 1][11], ans[N];

int main() {
	int n;
	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);
		pair<int, int> best = {0, 0};
		for (int j = 0; j < (1 << 10); j++)
			if (popcnt(a[i] & j) <= k[i] && k[i] - popcnt(a[i] & j) <= 10)
				best = max(best, dp[j][a[i] >> 10][k[i] - popcnt(a[i] & j)]);
		best.first++;
		ans[i] = best;
		for (int j = 0; j < (1 << 10); j++) {
			int cnt = popcnt((a[i] >> 10) & j);
			dp[a[i] & HM][j][cnt] = max(dp[a[i] & HM][j][cnt], {best.first, i});
		}
	}
	int idx = max_element(ans + 1, ans + n + 1) - ans;
	printf("%d\n", ans[idx].first);
	stack<int> seq;
	while (idx) {
		seq.push(idx);
		idx = ans[idx].second;
	}
	while (seq.size()) {
		printf("%d ", seq.top());
		seq.pop();
	}
	return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   12 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
subsequence.cpp:13:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |  for (int i = 1; i <= n; i++) scanf("%d", a + i);
      |                               ~~~~~^~~~~~~~~~~~~
subsequence.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |   scanf("%d", k + i);
      |   ~~~~~^~~~~~~~~~~~~

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