Submission #164791

#	Time	Username	Problem	Language	Result	Execution time	Memory
164791		mosiashvililuka	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	3 ms	632 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,f[100009],k[100009],dp[100009],pas1,pas2,nxt[100009],ka[1009],kaa[1009];
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a;
    for(b=1; b<=a; b++) cin>>f[b];
    for(b=1; b<=a; b++) cin>>k[b];
    for(b=a; b>=1; b--){
        dp[b]=1;
        if(dp[b]<ka[f[b]]){
            dp[b]=ka[f[b]];
            nxt[b]=kaa[f[b]];
        }
        for(c=0; c<256; c++){
            if(__builtin_popcount((f[b]&c))==k[b]&&ka[c]<dp[b]+1){
                ka[c]=dp[b]+1;
                kaa[c]=b;
            }
        }
        if(pas1<dp[b]){
            pas1=dp[b];
            pas2=b;
        }
    }
    cout<<pas1<<endl;
    while(pas2!=0){
        cout<<pas2<<" ";
        pas2=nxt[pas2];
    }
    return 0;
}

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