제출 #944991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
944991		TrendBattles	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	4835 ms	96788 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 < int > > > optimal(1 << DIV_B, vector < vector < int > > (1 << DIV_B, vector <int> (DIV_B + 1, -1)));

    vector <int> best(n + 1, -1);
    vector <int> dp(n + 1);

    int ans = 0, last = -1;
    for (int i = 1; i <= n; ++i) {
        dp[i] = 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) {
                int& pos = optimal[upper][r][coeff[i] - T];

                if (pos != -1 and maximise(dp[i], dp[pos] + 1)) {
                    best[i] = pos;
                }
            }
        }

        if (maximise(ans, dp[i])) {
            last = i;
        }

        for (int lower = 0; lower < (1 << DIV_B); ++lower) {
            int& pos = optimal[l][lower][bitcount[lower][r]];
            if (pos == -1 or dp[pos] < dp[i]) {
                pos = 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