Submission #944983

#	Time	Username	Problem	Language	Result	Execution time	Memory
944983		TrendBattles	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	4431 ms	130232 KiB

subsequence

//https://oj.uz/problem/view/IZhO17_subsequence

#include <bits/stdc++.h>
using namespace std;
using lli = int64_t;

const int DIV_B = 10;
int bitcount[1 << DIV_B][1 << DIV_B];

int maximise(int& x, int y) {
    if (x < y) return x = y, true;
    return false;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    for (int i = 0; i < (1 << DIV_B); ++i) {
        for (int j = 0; j < (1 << DIV_B); ++j) {
            bitcount[i][j] = __builtin_popcount(i & j);
        }
    }

    int n; cin >> n;
    vector <int> value(n + 1);
    for (int i = 1; i <= n; ++i) cin >> value[i];
    vector <int> coeff(n + 1);
    for (int i = 1; i <= n; ++i) cin >> coeff[i];

    vector < vector < vector < pair <int, int> > > > dp(1 << DIV_B, vector < vector < pair <int, int> > > (1 << DIV_B, vector <pair <int, int>> (DIV_B + 1, make_pair(0, -1))));

    vector <int> best(n + 1, -1);
    int ans = 0, last = -1;
    for (int i = 1; i <= n; ++i) {
        int max_len = 1, prv = -1;
        int l = value[i] >> DIV_B, r = value[i] & ~(-1LL << DIV_B);
        
        for (int upper = 0; upper < (1 << DIV_B); ++upper) {
            int& T = bitcount[upper][l];

            if (T <= coeff[i] and coeff[i] - T <= DIV_B and maximise(max_len, dp[upper][r][coeff[i] - T].first + 1)) {
                prv = dp[upper][r][coeff[i] - T].second;
            }
        }

        best[i] = prv;
        if (maximise(ans, max_len)) {
            last = i;
        }

        for (int lower = 0; lower < (1 << DIV_B); ++lower) {
            pair <int, int>& S = dp[l][lower][bitcount[r][lower]];
            if (maximise(S.first, max_len)) {
                S.second = i;
            }
        }
    }

    vector <int> v;
    while (last != -1) {
        v.push_back(last);
        last = best[last];
    }
    reverse(v.begin(), v.end());
    cout << ans << '\n';
    for (int x : v) cout << x << ' ';
    return 0;
}

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