Submission #314934

#	Time	Username	Problem	Language	Result	Execution time	Memory
314934		dolphingarlic	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5772 ms	92732 KiB

subsequence

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

const int HM = 1 << 10, N = 1e5 + 1;

int a[N], k[N];
pair<int, int> dp[HM][HM][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 < HM; 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 < HM; j++)
			dp[a[i] & HM - 1][j][popcnt((a[i] >> 10) & j)] = max(dp[a[i] & HM - 1][j][popcnt((a[i] >> 10) & j)], {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:23:17: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   23 |    dp[a[i] & HM - 1][j][popcnt((a[i] >> 10) & j)] = max(dp[a[i] & HM - 1][j][popcnt((a[i] >> 10) & j)], {best.first, i});
      |              ~~~^~~
subsequence.cpp:23:70: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   23 |    dp[a[i] & HM - 1][j][popcnt((a[i] >> 10) & j)] = max(dp[a[i] & HM - 1][j][popcnt((a[i] >> 10) & j)], {best.first, i});
      |                                                                   ~~~^~~
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