Submission #344192

#	Time	Username	Problem	Language	Result	Execution time	Memory
344192		IZhO_2021_I_want_Silver	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	2946 ms	97216 KiB

subsequence

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back

const int N = (1 << 20);
const int H = (1 << 10);
const int full = H - 1;

int n, a[N], k[N], pre[N], dp[H][H][11], pos[H][H][11], bits[N];
vector <int> vec;

int first10(int x) {
    return (x & full);
}

int last10(int x) {
    return (x >> 10);
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> k[i];
    }
    for (int i = 0; i < (1 << 20); ++i) {
        bits[i] = __builtin_popcount(i);
    }
    int ans = 0, ind = -1;
	for (int i = 1; i <= n; ++i) {
        int cur_ans = 0;
        pre[i] = -1;

        for (int mask = 0; mask < (1 << 10); ++mask) {
            int rem = k[i] - bits[mask & last10(a[i])];
            if (rem < 0 || 10 < rem) { continue; }

            if (cur_ans < dp[mask][first10(a[i])][rem]) {
                cur_ans = dp[mask][first10(a[i])][rem];
                pre[i] = pos[mask][first10(a[i])][rem];
            }
        }
        ++cur_ans;
        for (int mask = 0; mask < (1 << 10); ++mask) {
            if (dp[last10(a[i])][mask][bits[mask & first10(a[i])]] < cur_ans) {
                dp[last10(a[i])][mask][bits[mask & first10(a[i])]] = cur_ans;
                pos[last10(a[i])][mask][bits[mask & first10(a[i])]] = i;
            }
        }
        if (ans < cur_ans) {
            ans = cur_ans;
            ind = i;
        }
	}
	for (int x = ind; x != -1; x = pre[x]) { vec.pb(x); }
	reverse(all(vec));
	cout << sz(vec) <<"\n";
	for (int i = 0; i < sz(vec); ++i) { cout << vec[i] <<" "; }
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tests = 1;
	//cin >> tests;
	while (tests --) {
		solve();
	}
	return 0;
}
/*
    Just Chalish!
4
1 2 3 4
10 0 1 0

2
8 9
20 0

5
5 3 5 3 5
10 1 20 1 20
*/

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