제출 #1101662

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1101662		orcslop	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	1 ms	468 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }
bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

const int N = 1e5 + 5; 

int n; 
int a[N]; 
int k[N]; 
int p[N]; 
int dp[N]; 

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n; 
    for(int i = 1; i <= n; i++){
        cin >> a[i]; 
    }
    for(int i = 1; i <= n; i++){
        cin >> k[i]; 
    }
    fill(dp, dp + n + 1, 1); 
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            if(__builtin_popcount(a[i] & a[j]) == k[i]){
                if(ckmax(dp[i], dp[j] + 1)){
                    p[i] = j; 
                }
            }
        }
    }
    int ans = 0, curr = 0; 
    for(int i = 1; i <= n; i++){
        if(ckmax(ans, dp[i])){
            curr = i; 
        }
    }
    vector<int> ret; 
    while(curr){
        if(!ret.empty() && ret.back() == curr) break; 
        ret.push_back(curr); 
        curr = p[curr]; 
    }
    cout << ans << '\n'; 
    reverse(ret.begin(), ret.end()); 
    for(auto x : ret) cout << x << ' '; 
    return 0; 
}

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