Submission #1098562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098562		lampooppp	Longest beautiful sequence (IZhO17_subsequence)	C++17	7 / 100	105 ms	90476 KiB

subsequence

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

const int inf = 1e8;
const int mxp=(1<<10);
const int N=1e5;
int dp[mxp][mxp][11];
int last[mxp][mxp][11];
int trace[N+1];
int a[N+1],k[N+1];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i=0;i<mxp;++i)
    {
        for(int j=0;j<mxp;++j)
            for(int k=0;k<=10;++k) dp[i][j][k]=-inf;
    }
    for(int i=1;i<=n;++i)
    {
        cin >> a[i];
    }
    for(int i=1;i<=n;++i)
    {
        cin >> k[i];
    }
    int ans=0;
    int f=-1;
    for(int i=1;i<=n;++i)
    {
        //int x = a[i];
        int mx=1;
        int mask2 = a[i]&((1<<10)-1);
        int l=a[i]>>10;
        for(int mask =0;mask < (1<<10);++mask)
        {
            int x = (a[i]>>10)&mask;
            int p = __builtin_popcount(x);
            if(k[i]-p>__builtin_popcount(mask2)) continue;
            if(dp[mask][mask2][k[i]-p]+1>mx)
            {
                mx = dp[mask][mask2][k[i]-p]+1;
                trace[i] = last[mask][mask2][k[i]-p];
            }
            //mx=max(mx,dp[mask][mask2][k[i]-p]+1);
        }
        if(mx>ans)
        {
            ans=mx;
            f=i;
        }
        for(int mask=0;mask < (1<<10);++mask)
        {
            int p = __builtin_popcount(mask2&mask);
            if(mx > dp[l][mask][p])
            {
                dp[l][mask][p]=mx;
                last[l][mask][p]=i;
            }
            //dp[l][mask][p] = max(dp[l][mask][p],mx);
        }
    }
    cout << ans << '\n';
    stack<int> st;
    while(f!=0)
    {
        //cout << f << " ";
        st.push(f);
        f=trace[f];
    }
    while(!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    }
}

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