제출 #164792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
164792		mosiashvililuka	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	232 ms	3080 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];
    if(a<=5000){
    	for(b=a; b>=1; b--){
		dp[b]=1;
		for(c=b+1; c<=a; c++){
			if(__builtin_popcount(f[b]&f[c])==k[c]&&dp[b]<dp[c]+1){
				dp[b]=dp[c]+1;
				nxt[b]=c;
			}
		}
		if(pas1<dp[b]){
			pas1=dp[b];
			pas2=b;
		}
	}
	cout<<pas1<<endl;
	while(pas2!=0){
		cout<<pas2<<" ";
		pas2=nxt[pas2];
	}
	return 0;
	}
    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: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 0 / 60