Submission #716867

#	Time	Username	Problem	Language	Result	Execution time	Memory
716867		nonono	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2729 ms	253008 KiB

subsequence

#include "bits/stdc++.h"
#define SZ(x) (int)(x.size())
using namespace std;

const int mxN = 1e5 + 10;
const int mxM = 20 + 10;

int n, a[mxN], k[mxN], f[mxN];
int link[1 << 10][1 << 10];
pair<int, int> dp[1 << 10][1 << 10][mxM];

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) cin >> k[i];
    
    for(int i = 0; i < (1 << 10); i ++){
        for(int j = 0; j < (1 << 10); j ++){
            link[i][j] = __builtin_popcount(i & j);
        }
    }
    
    pair<int, int> res = {0, 0};
    for(int i = 1; i <= n; i ++){
        int l = a[i] >> 10; 
        int r = a[i] % (1 << 10);
        
        int tmp = 1;
        for(int mask = 0; mask < (1 << 10); mask ++){
            int A = link[l][mask];
            int B = k[i] - A;
            
            if(B < 0 || B > 10) continue ;
            if(dp[mask][r][B].first + 1 > tmp){
                tmp = dp[mask][r][B].first + 1;
                f[i] = dp[mask][r][B].second;
            }
        }
        
        if(res.first < tmp){
            res.first = tmp;
            res.second = i;
        }
        
        for(int mask = 0; mask < (1 << 10); mask ++){
            int A = link[r][mask];
            if(dp[l][mask][A].first < tmp){
                dp[l][mask][A].first = tmp;
                dp[l][mask][A].second = i;
            }
        }
    }
    
    cout << res.first << "\n";
    
    vector<int> s;
    for(int i = res.second; i > 0; i = f[i]) s.push_back(i);
    reverse(s.begin(), s.end());
    for(int x : s) cout << x << " ";
    
    return 0;
}

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