Submission #866653

#	Time	Username	Problem	Language	Result	Execution time	Memory
866653		Dec0Dedd	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	0 ms	604 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int N = 1e5+10;
const int K = 1024;
const int X = 10;

int p[N], a[N], x[N], n;
pii dp[K][2*X+1];

int main() {
    cin>>n;
    for (int i=1; i<=n; ++i) cin>>a[i];
    for (int i=1; i<=n; ++i) cin>>x[i];

    pii ans={1, 1};
    for (int i=1; i<=n; ++i) {
        int lf=a[i]&((1<<X)-1), rf=((a[i]>>X)&((1<<X)-1));

        pair<int, int> mx={0, 0};
        for (int lms=0; lms<K; ++lms) {
            int v=x[i]-__builtin_popcount(lms&lf);
            if (v < 0) continue;
            mx=max(mx, dp[lms][v]);
        } p[i]=mx.second;

        for (int rms=0; rms<K; ++rms) {
            int v=__builtin_popcount(rms&rf);
            dp[lf][v]=max(dp[lf][v], {mx.first+1, i});
        }
        ans=max(ans, {mx.first+1, i});
    }

    vector<int> v;
    int x=ans.second;
    while (x != 0) v.push_back(x), x=p[x];
    reverse(v.begin(), v.end());

    assert((int)v.size() == ans.first);
    cout<<ans.first<<"\n";
    for (auto u : v) cout<<u<<" ";
    cout<<"\n";
}

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