제출 #1098798

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098798		vjudge1	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	2721 ms	108900 KiB

subsequence

#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;
using ll=long long;
using pii=pair<int, int>;

const int N=1e5+13;
int n;
int a[N];
int k[N];
int dp[N];
pii sus[1024][1024][13];
int res;
int tr[N];
vector<int> v;

void scan(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    for(int i=1; i<=n; i++){
        cin >> k[i];
    }
}

void solve(){
    for(int i=1; i<=n; i++){
        pii pep=make_pair(0, 0);
        for(int pre=0; pre < 1024; pre++){
        	int z=__builtin_popcount(pre & (a[i] & 1023));
        	int cc=k[i]-z;
        	if(cc < 0 || cc >= 10) continue;
            pep=max(pep, sus[pre][a[i] >> 10][cc]);
        }
        dp[i]=pep.fi+1;
        tr[i]=pep.se;
        for(int suf=0; suf < 1024; suf++){
        	assert(__builtin_popcount(suf & (a[i] >> 10)) <= 10);
            sus[a[i] & 1023][suf][__builtin_popcount(suf & (a[i] >> 10))]=max(sus[a[i] & 1023][suf][__builtin_popcount(suf & (a[i] >> 10))], make_pair(dp[i], i));
        }
    }
    auto sus=max_element(dp+1, dp+n+1);
    cout << *sus << '\n';
    int id=sus-dp;
    while(id!=0){
        v.push_back(id);
        id=tr[id];
    }
    reverse(begin(v), end(v));
    for(int c: v) cout << c << ' ';
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    scan();
    solve();
}

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