제출 #742612

#제출 시각아이디문제언어결과실행 시간메모리
742612PoonYaPatLongest beautiful sequence (IZhO17_subsequence)C++14
100 / 100
3556 ms92884 KiB
#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][11];

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);

        for (int mask=0; mask<(1<<10); ++mask) {
            int cnt=__builtin_popcount(mask&fir);
            int want=b[i]-cnt;
            if (want>=0 && want<=10) {
                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 (mv) {
        temp.push_back(mv);
        mv=node[mv];
    }
    reverse(temp.begin(),temp.end());
    for (auto s : temp) cout<<s<<" ";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...