제출 #883524

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
883524		skywwla	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	87 ms	4696 KiB

subsequence

#include <bits/stdc++.h>

using namespace std ;
using ll = long long ;

int32_t main() {
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;
    int n ; cin >> n ;
    vector<int> a(n), k(n) ;
    for (int i = 0 ; i < n ; i++) cin >> a[i] ;
    for (int i = 0 ; i < n ; i++) cin >> k[i] ;
    if (n <= 5000) {
        vector<int> dp(n, 1), pr(n, -1) ;
        for (int i = 0 ; i < n ; i++) {
            for (int j = 0 ; j < i ; j++) {
                if (__builtin_popcount(a[i] & a[j]) == k[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1 ;
                    pr[i] = j ;
                }
            }
        }
        int pos = max_element(dp.begin(), dp.end()) - dp.begin() ;
        cout << dp[pos] << "\n" ;
        vector<int> res ;
        while (pos != -1) {
            res.push_back(pos) ;
            pos = pr[pos] ;
        }
        reverse(res.begin(), res.end()) ;
        for (int i : res) cout << i + 1 << ' ' ;
    } else {
        vector<int> dp(n, 1), pr(n, -1), last((1 << 8) + 1, -1) ;
        for (int i = 0 ; i < n ; i++) {
            for (int j = 0 ; j < (1 << 8) ; j++) {
                int cnt = __builtin_popcount(a[i] & j) ;
                if (cnt != k[i] || last[j] == -1) continue ;
                int l = last[j] ;
                if (dp[l] + 1 > dp[i]) {
                    dp[i] = dp[l] + 1 ;
                    pr[i] = l ;
                }
            }
            int &j = last[a[i]] ;
            if (j == -1 || dp[j] < dp[i]) j = i ;
        }
        int pos = max_element(dp.begin(), dp.end()) - dp.begin() ;
        cout << dp[pos] << "\n" ;
        vector<int> res ;
        while (pos != -1) {
            res.push_back(pos) ;
            pos = pr[pos] ;
        }
        reverse(res.begin(), res.end()) ;
        for (int i : res) cout << i + 1 << ' ' ;
    }
    return 0 ;
}

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