Submission #742603

#	Time	Username	Problem	Language	Result	Execution time	Memory
742603		PoonYaPat	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	7 ms	3016 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n,a[100001],b[100001],Ans,node[100001],mv;
pii dp[1<<10][1<<10][21]; //pii(val,index);

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for (int i=1; i<=n; ++i) cin>>a[i];
    for (int i=1; i<=n; ++i) cin>>b[i];

    for (int i=1; i<=n; ++i) {
        int ans=1;
        int fir=a[i]>>10, sec=a[i]%(1<<10);
        node[i]=i;

        for (int mask=0; mask<(1<<10); ++mask) {
            int cnt=__builtin_popcount((mask>>10)&fir);
            int want=b[i]-cnt;
            if (want>=0) {
                if (ans<dp[mask][sec][want].first+1) {
                    ans=dp[mask][sec][want].first+1;
                    node[i]=dp[mask][sec][want].second;
                }
            }
        }

        for (int mask=0; mask<(1<<10); ++mask) {
            int cnt=__builtin_popcount(sec&mask);
            if (ans>dp[fir][mask][cnt].first) {
                dp[fir][mask][cnt].first=ans;
                dp[fir][mask][cnt].second=i;
            }
        }

        if (ans>Ans) {
            Ans=ans;
            mv=i;
        }
    }

    cout<<Ans<<"\n";

    vector<int> temp;
    while (Ans--) {
        temp.push_back(mv);
        mv=node[mv];
    }
    reverse(temp.begin(),temp.end());
    for (auto s : temp) cout<<s<<" ";
}

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