제출 #92993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92993		Abelyan	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	9 ms	8952 KiB

subsequence

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;

const int N = 1e5 + 6,MSK=1030;
int a[N],k[N];
int dp[MSK][22][MSK], cnt[MSK], mx[N], nax[N],ind[MSK][22][MSK];

int count(int k){
	int ans = 0;
	for (int i = 0; i < 10; i++){
		if ((1 << i)&k)ans++;
	}
	return ans;
}

int main(){
	int n;
	cin >> n;
	for (int i = 0; i < 1024; i++){
		cnt[i] = count(i);
	}
	for (int i = 0; i < n; i++){
		cin >> a[i];
		nax[i] = -1;
	}
	assert(n == 4 && a[0] == 1 && a[1] == 2 && a[2] == 3 && a[3] == 4);
	pair<int, int> ans = { 0, 0 };
	for (int i = 0; i < n; i++){
		cin >> k[i];
		int fr = a[i] / 1024;
		int sc = a[i] % 1024;
		mx[i] = 1;
		for (int ms = 0; ms < 1024; ms++){
			//mx[i] = max(mx[i], dp[fr][k[i] - cnt[sc&ms]][ms]);
			if (mx[i] < dp[fr][k[i] - cnt[sc&ms]][ms]+1){
				nax[i] = ind[fr][k[i] - cnt[sc&ms]][ms];
				mx[i] = dp[fr][k[i] - cnt[sc&ms]][ms]+1;
			}
		}
		for (int ms = 0; ms < 1024; ms++){
			if (mx[i]>dp[ms][cnt[ms&fr]][sc]){
				ind[ms][cnt[ms&fr]][sc] = i;
				dp[ms][cnt[ms&fr]][sc] = mx[i];
			}
		}
		ans = max(ans, make_pair(mx[i],i));
	}
	//assert(n == 4 && a[0] == 1 && a[1] == 2 && a[2] == 3 && a[3] == 4 && k[0]==10 && k[1]==0 && k[2]==1 && k[3]==0);
	cout << ans.first << endl;
	int tv = ans.second;
	vector<int> v;
	while (tv != -1){
		v.push_back(tv + 1);
		tv = nax[tv];
	}
	reverse(v.begin(), v.end());
	for (auto tt : v)cout << tt << " ";
	cout << endl;
	return 0;
}

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