Submission #942019

#	Time	Username	Problem	Language	Result	Execution time	Memory
942019		12345678	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4852 ms	93432 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, kx=(1<<10);

int n, a[nx], k[nx];
pair<int, int> dp[kx][kx][11], res, p[nx];
vector<int> ans(1);

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>a[i], p[i]={1, INT_MAX};
    for (int i=1; i<=n; i++) cin>>k[i];
    for (int i=1; i<=n; i++)
    {
        int l=(a[i]/kx), r=a[i]&(kx-1);
        for (int j=0; j<kx; j++)
        {
            int left=(k[i]-(__builtin_popcount(j&l)));
            if (0<=left&&left<=10) p[i]=max(p[i], {dp[j][r][left].first+1, dp[j][r][left].second});
        }
        for (int j=0; j<kx; j++)
        {
            dp[l][j][__builtin_popcount(j&r)]=max(dp[l][j][__builtin_popcount(j&r)], {p[i].first, i});
        }
        if (p[i].first>res.first) res=p[i], ans[0]=i;
    }
    cout<<res.first<<'\n';
    while (res.second!=INT_MAX) ans.push_back(res.second), res=p[res.second];
    reverse(ans.begin(), ans.end());
    for (auto x:ans) cout<<x<<' ';
}

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