제출 #1124353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124353		I_FloPPed21	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	2814 ms	95980 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
const int bits=10,N=1e5+1;
struct dinamica
{
    int len,fin;
};
int v[N],n,conditie[N],compari[(1<<bits)][(1<<bits)],predecesor[N];
dinamica dp[1<<bits][1<<bits][bits+1];
void citeste()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>v[i];
    for(int i=1; i<=n; i++)
        cin>>conditie[i];
    for(int i=1; i<=n; i++)
        predecesor[i]=i;
}
void precalc()
{
    for(int i=0; i<(1<<bits); i++)
        for(int j=0; j<(1<<bits); j++)
            compari[i][j]=__builtin_popcount(i&j);
}
void calculate()
{
    int best_where=0;
    int ans=0;
    for(int i=1; i<=n; i++)
    {
        int stanga=(v[i]>>bits);
        int dreapta=(v[i]%(1<<bits));

        int best=1;
        for(int k=0; k<(1<<bits); k++)
        {
            int need=conditie[i]-compari[k][stanga];
            if(need<0||need>bits)
                continue;

            if(dp[k][dreapta][need].len+1>best)
            {
                predecesor[i]=dp[k][dreapta][need].fin;
                best=dp[k][dreapta][need].len+1;
            }
        }//alegem practic ce e mare
        if(best>ans)
        {
            ans=best;
            best_where=i;
        }
        for(int k=0;k<(1<<bits);k++)
        {
            if(dp[stanga][k][compari[dreapta][k]].len<best)
            {
                dp[stanga][k][compari[dreapta][k]].fin=i;
                dp[stanga][k][compari[dreapta][k]].len=best;
            }
        }
    }
    cout<<ans<<'\n';
    vector<int>afis;
    while(predecesor[best_where]!=best_where)
    {
        afis.push_back(best_where);
        best_where=predecesor[best_where];
    }
    afis.push_back(best_where);
    reverse(afis.begin(),afis.end());
    for(auto u:afis)
        cout<<u<<" ";
    cout<<'\n';

}
int main()
{
    citeste();
    precalc();
    calculate();
    return 0;
}

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