Submission #1265618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265618		herreinstein	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	1997 ms	96456 KiB

subsequence

#include <bits/stdc++.h>
//#define int long long int
#define ff first
#define ss second
const int MOD = 998244353;
const int N = 2e5 + 5;
using namespace std;
int a[N], b[N];
pair<int, int> dp[N];
pair<int, int> pre[1024][1024][11];
int pop[1024][1024];
void solve(){
    int n;
    cin >> n;
    pair<int, int> maxx = {0, 0};
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int i = 0; i < 1024; i++) for(int j = 0; j < 1024; j++) pop[i][j] = __builtin_popcount(i&j);
    for(int i = 1; i <= n; i++){
        pair<int, int> mx = {0, -1};
        int ilk = (a[i] >> 10), son = a[i] % 1024;
        for(int j = 0; j < 1024; j++){
            int kalan = b[i] - pop[ilk][j];
            if(kalan >= 0 && kalan <= 10){
                if(mx.ff < pre[j][son][kalan].ff) mx = pre[j][son][kalan];
            }
        }
        dp[i] = mx; dp[i].ff++;
        for(int j = 0; j < 1024; j++){
            if(pre[ilk][j][pop[j][son]].ff < dp[i].ff){
                pre[ilk][j][pop[j][son]] = {dp[i].ff, i};
            }
        }
        if(maxx.ff < dp[i].ff) maxx = {dp[i].ff, i};
    }
    int k = maxx.ss;
    vector<int> pth;
    while(dp[k].ss != -1){
        pth.push_back(k);
        k = dp[k].ss;
    }
    pth.push_back(k);
    cout << pth.size() << endl;
    for(int i = pth.size()-1; i > -1; i--) cout << pth[i] << " ";
    cout << endl;
}
int32_t main(){
    
    int t;
    // cin >> t;
    t = 1;
    while(t--) solve();
}

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