Submission #1134985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134985		sitingfake	Longest beautiful sequence (IZhO17_subsequence)	C++20	23 / 100	6094 ms	1496 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
#define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s";
#define ll long long
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) ((x>>(i))&1)
#define off(x,i) (x^(1<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define sitingfake 1
#define orz 1
const int mod=1e9+7;
const long long linf=1e18+3;
const int inf=1e9;
const int maxarr=1e6+5;
const double pi=acos(-1);
const int dx[]={0,1,-1,0};
const int dy[]={1,0,0,-1};
const int maxn=2e5+7;
int n;
int a[maxn],k[maxn];
namespace sub2
{
    int dp[maxn];
    ii ans;
    void trace(int i)
    {
        if(dp[i]==1)
        {
            cout<<i<<" ";
            return;
        }
        else
        {
            for(int j=i-1;j>=1;j--)
            {
                int val=a[i]&a[j];
                if(__builtin_popcount(val)==k[i]&&dp[j]==dp[i]-1)
                {
                    trace(j);
                    cout<<i<<" ";
                    break;
                }
            }
        }
    }
    void solve()
    {
        for(int i=1;i<=n;i++)
        {
            dp[i]=1;
            for(int j=i-1;j>=1;j--)
            {
                int val=a[i]&a[j];
                if(__builtin_popcount(val)==k[i])
                {
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
            if(dp[i]>ans.fi)
            {
                ans.fi=dp[i];
                ans.se=i;
            }
        }
        cout<<ans.fi<<"\n";
        trace(ans.se);
    }
}
signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   cin>>n;
   for(int i=1;i<=n;i++) cin>>a[i];
   for(int i=1;i<=n;i++) cin>>k[i];
   sub2::solve();
   //execute;
}
/*
5
5 3 5 3 5
10 1 20 1 20
*/

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