Submission #36964

#	Time	Username	Problem	Language	Result	Execution time	Memory
36964		szawinis	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	4976 ms	49164 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+1, M = 1 << 10;

int n, a[N], k[N], cnt[N], res[N], trace[N], dp[M][M][11];
vector<int> ord;
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 x = 0; x < M; x++) cnt[x] = __builtin_popcount(x);
	for(int i = 1; i <= n; i++) {
		res[i] = 1;
		int pref = a[i] >> 10, suff = a[i] - (pref << 10);
		// fix pref & x, find optimal idx such that when AND with suff, produces bitcount == residue
		// note that pref & x must be a prefix of a[idx] by the algorithm's nature
		for(int x = 0; x < M; x++) {
			int residue = k[i] - cnt[pref & x];
			if(residue < 0 || residue > 10) continue;
			int idx = dp[x][suff][residue];
			if(res[idx] + 1 > res[i]) {
				res[i] = res[idx] + 1;
				trace[i] = idx;
			}
		}
		// fix suff & x, and update accordingly
		for(int x = 0; x < M; x++) {
			int new_suff = suff & x;
			if(res[i] > res[dp[pref][x][cnt[new_suff]]])
				dp[pref][x][cnt[new_suff]] = i;
		}
	}
	int idx = max_element(res+1, res+n+1) - res;
	for(int i = idx; i > 0; i = trace[i]) ord.push_back(i);
	reverse(ord.begin(), ord.end());
	printf("%d\n", res[idx]);
	for(int i: ord) printf("%d ", i);
}

Compilation message (stderr)

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

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