제출 #859788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
859788		phongcd	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	2576 ms	105408 KiB

subsequence

#include <bits/stdc++.h>
#define ll long long
#define ld long  double
#define ull unsigned long long
#define ii pair <int, int>
#define ill pair <ll, ll>
#define ild pair <ld, ld>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define file "test"
using namespace std;
const int N = 1e5 + 2;
const int M = 10;
const ll MOD = 998244353;
const ll INF = 1e18;
const ll base = 311;
const int BLOCK_SIZE = 400;
 
int n;
int a[N], b[N];
int cnt[1 << M][1 << M];
ii f[1 << M][1 << M][12];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    for (int i = 0; i < (1 << M); i ++)
        for (int j = 0; j < (1 << M); j ++)
            cnt[i][j] = __builtin_popcount(i & j);

    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++) cin >> b[i];

    vector <int> trace(n + 1);
    
    int ans = 1, k = 1;
    for (int i = 1; i <= n; i ++) {
        int l = a[i] >> M;
        int r = a[i] & ((1 << M) - 1);
        
        int cur = 1;
        for (int s = 0; s < (1 << M); s ++) {
            int w = b[i] - cnt[s][l];
            if (0 > w || w > M) continue;
            if (f[s][r][w].fi + 1 > cur)
                cur = f[s][r][w].fi + 1, trace[i] = f[s][r][w].se;
        }

        if (cur > ans)
            ans = cur, k = i;

        for (int s = 0; s < (1 << M); s ++) 
            if (f[l][s][cnt[s][r]].fi < cur) 
                f[l][s][cnt[s][r]] = {cur, i};
    }

    cout << ans << '\n';
    vector <int> res;
    while (k > 0) {
        res.push_back(k);
        k = trace[k];
    }
    reverse(all(res));
    for (int u: res) cout << u << ' ';
}
/*
     /\_/\ zzZ
    (= -_-)
    / >u  >u
*/

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