Submission #1321703

#TimeUsernameProblemLanguageResultExecution timeMemory
1321703LudisseyLongest beautiful sequence (IZhO17_subsequence)C++20
100 / 100
3282 ms92852 KiB
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;

const int LOG=10;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    vector<int> a(n);    
    vector<int> k(n);    
    vector<int> v(n);    
    vector<int> prev(n,-1);    
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> k[i];
    vector<vector<vector<pair<int,int>>>> dp((1<<LOG), vector<vector<pair<int,int>>>(LOG+1,vector<pair<int,int>>((1<<LOG),{0,-1})));
    for (int i = 0; i < n; i++)
    {
        int aL=a[i]%((1<<LOG));
        int aR=a[i]/((1<<LOG));
        v[i]=1;
        for (int b = 0; b < (1<<LOG); b++)
        {
            int bp=__builtin_popcount(aR&b);
            if(bp>k[i]||k[i]-bp>LOG) continue;
            int vl=dp[aL][k[i]-bp][b].first+1;
            if(vl>v[i]) prev[i]=dp[aL][k[i]-bp][b].second;
            v[i]=max(v[i],vl);
        }
        for (int b = 0; b < (1<<LOG); b++)
        {
            int bp=__builtin_popcount(aL&b);
            if(v[i]>dp[b][bp][aR].first) dp[b][bp][aR]={v[i],i};
        }
    }
    int x=max_element(all(v))-v.begin();
    cout << v[x] << "\n";
    vector<int> outp;
    while(x>=0){
        outp.push_back(x);
        x=prev[x];
    }
    for (int i = sz(outp)-1; i >= 0; i--) cout << outp[i]+1 << " ";
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...