Submission #1098571

#TimeUsernameProblemLanguageResultExecution timeMemory
1098571lampoopppLongest beautiful sequence (IZhO17_subsequence)C++17
100 / 100
2673 ms92928 KiB
#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()
{
  //  freopen("subsequence.in", "r", stdin);
  //  freopen("subsequence.out", "w", stdout);
    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) continue;
            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';
//    if(ans==361)
//    {
//        cout << a[477] << " " << a[528] << " " << k[528] << " " << (a[477]&a[528]) << '\n';
//    }
    stack<int> st;
    while(f!=0)
    {
        //cout << f << " ";
        st.push(f);
        f=trace[f];
    }
    while(!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...