Submission #1267627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267627		Hamed_Ghaffari	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	2238 ms	92288 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;

#define pop __builtin_popcount

const int MXN = 1e5 + 5;

int n, a[MXN], k[MXN], dp[1<<10][1<<10][11], par[1<<10][1<<10][11], ans[MXN], f[MXN];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    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++) {
        ans[i] = 1;
        f[i] = 0;
        int a1 = a[i]>>10, a2 = a[i]&((1<<10)-1);
        for(int b1=0; b1<(1<<10); b1++) {
            int p = pop(a1&b1);
            if(p<=k[i] && k[i]-p<=10 && dp[b1][a2][k[i]-p]+1>ans[i]) {
                ans[i] = dp[b1][a2][k[i]-p]+1;
                f[i] = par[b1][a2][k[i]-p];
            }
        }
        for(int b2=0; b2<(1<<10); b2++) {
            int p = pop(a2&b2);
            if(ans[i]>dp[a1][b2][p]) {
                dp[a1][b2][p] = ans[i];
                par[a1][b2][p] = i;
            }
        }
    }
    vector<int> res;
    for(int i=max_element(ans+1, ans+n+1)-ans; i; i=f[i])
        res.push_back(i);
    cout << res.size() << '\n';
    while(!res.empty()) {
        cout << res.back() << ' ';
        res.pop_back();
    }
    cout << '\n';
    return 0;
}

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