Submission #703887

#	Time	Username	Problem	Language	Result	Execution time	Memory
703887		Denkata	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3686 ms	93084 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
const int M = (1<<10);
const int maxn = 1e5+3;
int i,j,p,q,n,m,a[maxn],k[maxn],previous[maxn];
pair<int,int> dp[M][M][11],ans;///fixed (previous) left half,(current) right half, number of bits for & with the right half
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    for(i=1;i<=n;i++)
        cin>>k[i];
    for(i=1;i<=n;i++)
    {
        pair <int,int> cur={0,0};
        int left = (a[i]>>10);
        int right = (a[i]&((1<<10)-1));
        for(j=0;j<M;j++)
        {
            int ost = k[i]-__builtin_popcount(j&left);
            if(ost<0 || ost>10)continue;
            cur = max(cur,dp[j][right][ost]);
        }
        cur.first++;
        previous[i] = cur.second;
        cur.second = i;
        ans=max(ans,cur);
        for(int j=0;j<M;j++)
        {
            p = __builtin_popcount(j&right);
            dp[left][j][p]=max(cur,dp[left][j][p]);
        }
    }
    cout<<ans.first<<endl;
    p=ans.second;
    stack <int> s;
    while(p>0)
    {
        s.push(p);
        p=previous[p];
    }
    while(!s.empty())
    {
        cout<<s.top()<<" ";
        s.pop();
    }
    return 0;
}

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