제출 #1122546

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

subsequence

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

//#define int long long

#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sp <<' '<<
#define pb push_back

#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)

#define cont(a) for(auto el:a) cout<<el<<' '; cout<<endl;
#define contp(a) for(auto el:a) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;

#define DEBUG(x) cout<<#x sp ":" sp x<<endl;

typedef vector<int> vi;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef long long ll;

#define mid (l+r)/2

#define topla(x,y) ((x%MOD)+(y%MOD))%MOD
#define carp(x,y) ((x%MOD)*(y%+MOD))%MOD

const int MAXN=300;

int n;
vi a,k;

pii dp[MAXN];
//dp[i]-->{i.sayıyla biten max lengthli array ve bir önceki eleman}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    a.resize(n+1);
    k.resize(n+1);

    int mx=0;
    FORE(i,1,n+1){
        cin>>a[i];
        mx=max(mx,a[i]);
    }
    FORE(i,1,n+1) cin>>k[i];

    if(mx<300){ //3.subtask
        pii cev={1,0};

        vb used(300,false);
        used[1]=true;
        
        FORE(i,1,n+1){
            pii tut={1,0};
            FOR(j,256){
                if(__builtin_popcount(j&a[i])!=k[i]) continue;
                if(!used[j]) continue;

                //cout<<"here" sp j sp a[i] sp k[i]<<endl;

                if(dp[j].fi+1>tut.fi){
                    tut.fi=dp[j].fi+1;
                    tut.se=j;
                }
            }

            dp[i]=tut;

            if(dp[i].fi>cev.fi){
                cev.fi=dp[i].fi;
                cev.se=i;
            }

            used[a[i]]=true;
        }

        //DEBUG(cev.fi);
        //DEBUG(cev.se);

        cout<<cev.fi<<endl;
        vi route;
        while(dp[cev.se].se!=0){
            route.pb(cev.se);
            cev.se=dp[cev.se].se;
        }

        route.pb(1);
        reverse(all(route));

        cont(route);
    }
    /*else{ //1 ve 2. subtask

    }*/
}       

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