Submission #337931

#	Time	Username	Problem	Language	Result	Execution time	Memory
337931		BY_KUTBILIM	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	6084 ms	1900 KiB

subsequence

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

#define ff first
#define ss second
#define pb push_back
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).end()

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie();

    int n;
    cin >> n;
    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];
    vector<int> dp(n, 1);
    vector<int> p(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]){
                if(dp[i] < dp[j] + 1){
                    dp[i] = dp[j] + 1;
                    p[i] = j;
                }
            }
        }
    }
    int ans = 0;
    int I = 0;
    for(int i = 0; i < n; i++){
        if(dp[i] > ans){
            ans = dp[i];
            I = i;
        }
    }
    vector<int> path;
    while(I != -1){
        path.pb(I + 1);
        I = p[I];
    }
    cout << ans << endl;
    reverse(all(path));
    for(auto v : path){
        cout << v << " ";
    }

    return 0;
}

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