Submission #502456

#	Time	Username	Problem	Language	Result	Execution time	Memory
502456		wwdd	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	2304 ms	47248 KiB

subsequence

//""""optimized"""" lol
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vl;
const int MB = 10;
const int MA = 1<<MB;
const int LIM = MA-1;
int dp[MA][MA][MB+1];
const int MN = 100001;
int mol[MN],pt[MN],wo[MN],wk[MN];
int poc[MA];
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	ll n;
	cin >> n;
	memset(mol,0,sizeof(mol));
	memset(pt,-1,sizeof(pt));
	memset(dp,-1,sizeof(dp));
	for(int i=0;i<n;i++) {
		cin >> wo[i];
	}
	for(int i=0;i<n;i++) {
		cin >> wk[i];
	}
	poc[0] = 0;
	for(int i=1;i<MA;i++) {
		poc[i] = poc[i>>1]+(i&1);
	}
	for(int i=0;i<n;i++) {
		int ho = wo[i]>>MB;
		int lo = wo[i]&LIM;
		mol[i] = 1;
		for(int j=0;j<MA;j++) {
			int rem = wk[i]-poc[ho&j];
			if(rem < 0 || rem > MB) {continue;}
			int cand = dp[j][lo][rem];
			if(cand == -1) {continue;}
			if(mol[cand]+1 > mol[i]) {
				mol[i] = mol[cand]+1;
				pt[i] = cand;
			}
		}
		for(int j=0;j<MA;j++) {
			int kt = poc[j&lo];
			int dv = dp[ho][j][kt];
			if(dv == -1 || mol[dv] < mol[i]) {
				dp[ho][j][kt] = i;
			}
		}
	}
	int mi = 0;
	for(int i=0;i<n;i++) {
		if(mol[i] > mol[mi]) {
			mi = i;
		}
	}
	vl ans;
	while(mi != -1) {
		ans.push_back(mi);
		mi = pt[mi];
	}
	reverse(ans.begin(),ans.end());
	cout << ans.size() << '\n';
	for(int i=0;i<ans.size();i++) {
		if(i > 0) {cout << " ";}
		cout << ans[i]+1;
	}
	cout << '\n';
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:65:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=0;i<ans.size();i++) {
      |              ~^~~~~~~~~~~

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