Submission #331674

#TimeUsernameProblemLanguageResultExecution timeMemory
331674vitkishloh228Longest beautiful sequence (IZhO17_subsequence)C++14
0 / 100
2 ms748 KiB
#include<iostream>
#include<vector>
#include<algorithm>
#include<bitset>
using namespace std;
const int maxc = 10000;
const int logn = 10;
int dp[(1 << logn) + 1][(1 << logn) + 1][logn + 1];
int back[(1 << logn) + 1][(1 << logn) + 1][logn + 1];
int cot(int x) {
	int ans = 0;
	for (int i = 2 * logn; i >= 0; i--) {
		if ((x & (1 << i))) ans++;
	}
	return ans;
}
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<int>k(n);
    for (int i = 0; i < n; ++i) {
        cin >> k[i];
    }
    vector<int> dp2(n);
    vector<int> back2(n, -1);
    for (int i = 0; i < n; ++i) {
        dp2[i] = 1;
        int val = a[i] & 1023;
        int val2 = (a[i] - val) / 1024;
		for (int j = 0; j < 1024; j++) {
			if (cot(j & val) > k[i]) {
				continue;
			}
			if (k[i] - cot(j & val) > 10) {
				continue;
			}
			if (dp[j][val2][k[i] - cot(j & val)] + 1 > dp2[i]) {
				back2[i] = back[j][val2][k[i] - cot(j & val)];
			}
			dp2[i] = max(dp2[i], dp[j][val2][k[i] - cot(j & val)] + 1);
		}
		for (int j = 0; j < 1024; j++) {
			if (dp2[i] > dp[val][j][cot(j & val2)]) {
				back[val][j][cot(j & val2)] = i;
			}
			dp[val][j][cot(j & val2)] = max(dp[val][j][cot(j & val2)], dp2[i]);
		}
    }
	int j = 0;
	for (int i = 0; i < n; ++i) {
		if (dp2[i] > dp2[j]) j = i;
	}
	vector<int> ans;
	for (int i = j; i != -1; i = back2[i]) {
		ans.push_back(i + 1);
	}
	cout << ans.size() << endl;
	for (auto elem : ans) cout << elem << ' ';
 }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...