Submission #229641

#	Time	Username	Problem	Language	Result	Execution time	Memory
229641		farmerboy	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5046 ms	48632 KiB

subsequence

/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/
 
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x
 
using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;
 
const ll MODBASE = 1000000007LL;
const int MAXN = 100010;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;

int n, a[MAXN], k[MAXN], f[1<<10][1<<10][11];
II dp[MAXN];
vector<int> kq;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n;
    FOR(i,1,n) cin >> a[i];
    FOR(i,1,n) cin >> k[i];

    FOR(i,0,(1<<10)-1)
        FOR(j,0,(1<<10)-1)
            FOR(bits,0,10) f[i][j][bits] = -1;

    II res = II(0,0);
    FOR(i,1,n) {
        int firstHalf = a[i] & ((1 << 10) - 1), secondHalf = a[i] >> 10;
        dp[i] = II(1, -1);
        FOR(prevFirstHalf,0,(1<<10)-1) {
            int firstHalfSetBits = __builtin_popcount(prevFirstHalf & firstHalf);
            int secondHalfSetBits = k[i] - firstHalfSetBits;
            if (secondHalfSetBits < 0 || secondHalfSetBits > 10) continue;
            int prevPos = f[prevFirstHalf][secondHalf][secondHalfSetBits];
            if (prevPos == -1) continue;
            dp[i] = max(dp[i], II(dp[prevPos].FI + 1, prevPos));
        }
        res = max(res, II(dp[i].FI, i));
        FOR(nextSecondHalf,0,(1<<10)-1) {
            int secondHalfSetBits = __builtin_popcount(nextSecondHalf & secondHalf);
            int &trace = f[firstHalf][nextSecondHalf][secondHalfSetBits];
            if (trace != -1 && dp[trace].FI > dp[i].FI) continue;
            trace = i;
        }
    }

    cout << res.FI << "\n";
    kq.push_back(res.SE);
    while (dp[kq.back()].SE != -1) kq.push_back(dp[kq.back()].SE);
    reverse(ALL(kq));
    for (int x : kq) cout << x << ' ';
    return 0;
}

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