Submission #697883

#	Time	Username	Problem	Language	Result	Execution time	Memory
697883		Tam_theguide	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3826 ms	93188 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define fi first
#define se second
const int N = 10;
const int M = 1e5 + 5;
int n, a[M], k[M], pv[M];
pii dp[(1<<N)+2][(1<<N)+2][11], ans;
vector<int> res;
int main() {
    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 = 1; i <= n; i++) {
        int rhs = a[i]&((1<<N)-1);
        int lhs = ((a[i]-rhs)>>N);
        pii tmp = {0, 0};
        for (int mask = 0; mask < (1<<N); mask++) {
            int l_and = __builtin_popcount(lhs&mask);
            l_and = k[i]-l_and;
            if (l_and < 0 || l_and > 10) continue;
            if (dp[mask][rhs][l_and].fi > tmp.fi) tmp = dp[mask][rhs][l_and];
        }
        tmp.fi++;
        pv[i]=tmp.se;
        tmp.se=i;
        if (tmp.fi > ans.fi) ans = tmp;
        for (int mask = 0; mask < (1<<N); mask++) {
            int r_and = __builtin_popcount(rhs&mask);
            if (tmp.fi > dp[lhs][mask][r_and].fi) dp[lhs][mask][r_and] = tmp;
        }
    }
    cout << ans.fi << '\n';
    int cur = ans.se;
    while (cur) {
        res.push_back(cur);
        cur = pv[cur];
    }
    reverse(res.begin(), res.end());
    for (auto c: res) cout << c << " ";
}
/*
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