Submission #51648

#	Time	Username	Problem	Language	Result	Execution time	Memory
51648		Nicksechko	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5809 ms	159440 KiB

subsequence

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;

const int MAXN = 120000;

int dp[1 << 10][1 << 10][11];
int go[1 << 10][1 << 10][11];
int go2[MAXN];
int dp2[MAXN];
vector<int> vv;
int n;
int a[MAXN];
int k[MAXN];
int pc[1 << 20];

int main() {
//    freopen("subsequence.in", "r", stdin);
//	freopen("subsequence.out", "w", stdout);
	for (int i = 0; i < (1 << 20); ++i)
		pc[i] = __builtin_popcount(i);
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%d", a + i);
	for (int i = 0; i < n; ++i)
		scanf("%d", k + i);
	int gans = 0;
	int gen = -1;
	for (int i = 0; i < n; ++i) {
		int pr = -1;
		int ans = 0;
		int kk = k[i];
		int x = (a[i] >> 10);
		int y = a[i] - (x << 10);
		for (int j = 0; j < (1 << 10); ++j) {
			int c = pc[x & j];
			if (c <= kk && kk - c <= 10) {
				if (dp[j][y][kk - c] > ans)
					ans = dp[j][y][kk - c], pr = go[j][y][kk - c];
			}
		}
		dp2[i] = ans + 1;
		go2[i] = pr; 
		if (ans + 1 > gans)
			gans = ans + 1, gen = i;
		for (int j = 0; j < (1 << 10); ++j) {
			int c = pc[j & y];
			if (dp2[i] > dp[x][j][c])
				dp[x][j][c] = dp2[i], go[x][j][c] = i;
		}
	}
	int now = gen;
	while (now != -1)
		vv.push_back(now), now = go2[now];
	reverse(vv.begin(), vv.end());
	printf("%d\n", (int)vv.size());
	for (int i = 0; i < vv.size(); ++i) {
		printf("%d ", vv[i] + 1);
	}
	printf("\n");
	return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vv.size(); ++i) {
                  ~~^~~~~~~~~~~
subsequence.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
subsequence.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
   ~~~~~^~~~~~~~~~~~~
subsequence.cpp:45: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