제출 #944983

#제출 시각아이디문제언어결과실행 시간메모리
944983TrendBattlesLongest beautiful sequence (IZhO17_subsequence)C++14
100 / 100
4431 ms130232 KiB
//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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...