Submission #1346776

#TimeUsernameProblemLanguageResultExecution timeMemory
1346776anarch_yLongest beautiful sequence (IZhO17_subsequence)C++20
100 / 100
3421 ms100568 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

pair<int, int> dp1[(1<<20)];
pair<int, int> dp2[(1<<10)][(1<<10)][11];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    vector<int> a(n+1), k(n+1);
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) cin >> k[i];
    int dp[n+1] = {}, b[n+1] = {};
    for(int i=1; i<=n; i++){
        int m = a[i];
        int y = (a[i]&((1<<10)-1));
        int x = ((a[i]^y)>>10);
        pair<int, int> pr;
        for(int x1=0; x1<(1<<10); x1++){
            int k1 = __builtin_popcount((x&x1));
            if(k1 > k[i] or k[i]-k1 > 10) continue;
            pr = max(pr, dp2[x1][y][k[i]-k1]);
        }
        if(pr.first == 0){
            dp[i] = 1;
        }
        else{
            dp[i] = pr.first + 1;
            b[i] = pr.second;
        }
        dp1[m] = max(dp1[m], {dp[i], i});
        for(int y1=0; y1<(1<<10); y1++){
            int k1 = __builtin_popcount((y&y1));
            dp2[x][y1][k1] = max(dp2[x][y1][k1], dp1[m]);
        }
    }
    int ans = 0, c = 0;
    for(int i=1; i<=n; i++){
        if(dp[i] > ans){
            ans = dp[i];
            c = i;
        }
    }
    cout << ans << "\n";
    vector<int> v;
    while(c != 0){
        v.pb(c);
        c = b[c];
    }
    reverse(all(v));
    for(auto e: v) cout << e << ' ';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...