제출 #1368941

#제출 시각아이디문제언어결과실행 시간메모리
1368941mhn_neekLongest beautiful sequence (IZhO17_subsequence)C++20
40 / 100
6089 ms6112 KiB
//In the name of God
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")

using namespace std;
typedef int lli;
typedef pair<lli,lli> pii;
typedef vector<lli> ve;
const lli N=1e5+100;
#define all(v) v.begin(),v.end()
#define migmig ios_base::sync_with_stdio(false),cout.tie(0), cin.tie(0);
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define FOR(x,n) for(lli x = 0; x < n; x++)
#define FORS(x,n) for(lli x = 1; x <= n; x++)
#define endl "\n"
#define sep " "
#define SZ(X) (lli)X.size()
#define debug(x) cerr << (#x) << " " << (x) << endl

lli tmp;
lli n,A[N],k[N];
lli cnt[(1 << 21)];
pii dp[N];
int main(){
    migmig;
    FOR(i,(1 << 20)){
        cnt[i] = __builtin_popcount(i);
    }
    cin>>n;
    FORS(i,n){
        cin>>A[i];
    }
    FORS(i,n){
        cin>>k[i];
    }

    FORS(i,n){
        pii p;
        FORS(j,i-1){
            if(cnt[A[i]&A[j]] == k[i]){
                p.fi = dp[j].fi + 1,p.se = j;
                dp[i] = max(dp[i],p);
            }
        }

    }

    lli ans = 0;
    lli las = 0;
    FORS(i,n){
        ans = max(ans,dp[i].fi);
        if(ans == dp[i].fi)las = i;
    }

    ve v;
    while(las > 0){
        v.PB(las);
        las = dp[las].se;
    
    }

    cout<<SZ(v)<<endl;
    reverse(all(v));
    for(auto i : v)cout<<i<<" ";

}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…