Submission #841551

#	Time	Username	Problem	Language	Result	Execution time	Memory
841551		Elvin_Fritl	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	41 ms	808 KiB

subsequence

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

const int N = 5050 , inf = 1e9 + 199;

int dp[N],ind[N];

int32_t main()
{

    int n;
    cin>>n;
    assert(n <= 5000);
    vector<int>a(n+1),k(n+1);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        cin>>k[i];
    }
    dp[1]=1;
    for(int i=2;i<=n;i++){
        int maxi = 0 , indd = 1;
        if((a[i-1]) >= k[i-1]){
            for(int j=i-1;j>=1;j--){
                if(__builtin_popcount((a[i-1]&a[j-1])) == k[i-1]){
                    if(dp[j]+1 > maxi) {
                        maxi = dp[j]+1;
                        indd = j;
                    }
                }
            }
        }
        if(maxi > 0){
            dp[i] = maxi;
            ind[i] = indd;
        }
        else{
            dp[i]=1;
            ind[i] = 0;
        }
    }
    int maxi = 0 , indd = 1;
    for(int i=1; i<=n; i++){
        if(dp[i] >= maxi){
            maxi = dp[i];
            indd = i;
        }
    }
    vector<int> res;
    while(indd != 0){
        res.push_back(indd);
        indd = ind[indd];
    }
    cout<<res.size()<<endl;
    sort(res.begin(), res.end());
    for(int i:res){
        cout<<i<<" ";
    }

}

/*



*/

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