제출 #147168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
147168		abacaba	Longest beautiful sequence (IZhO17_subsequence)	C++14	7 / 100	6083 ms	172928 KiB

subsequence

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;
 
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>

const int inf = 2e9; 
const int N = 1e5 + 15;
const int M = 1 << 10;
const int K = 21;
int n, m, a[N], k[N], dp[N], f[2][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);
		}
		memcpy(f[bit], f[bit ^ 1], sizeof(f[bit]));
		for(int mask = 0; mask < M; ++mask) {
			int k2 = k[i] - cntbit(mask & first_half);
			if(k2 >= 0 && dp[f[bit][mask][second_half][k2]] + 1 > dp[i])
				dp[i] = dp[f[bit][mask][second_half][k2]] + 1,
				back[i] = f[bit][mask][second_half][k2];
		}
		for(int mask = 0; mask < M; ++mask) {
			int k1 = cntbit(mask & second_half);
			if(dp[i] > dp[f[bit][first_half][mask][k1]])
				f[bit][first_half][mask][k1] = i;
		}
	}
	int ans = max_element(dp + 1, dp + 1 + n) - dp;
	printf("%d\n", dp[ans]);
	rec(ans);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

subsequence.cpp: In function 'int main()':
subsequence.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
subsequence.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
subsequence.cpp:53: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: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60