Submission #1232832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232832		Bahamin	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	3563 ms	92288 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
const int MAX_N = 1e5 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;

pair<int, int> dp[(1 << 10)][(1 << 10)][11];
pair<int, int> dp1[MAX_N];

void solve() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    int k[n];
    for (int i = 0; i < n; i++) cin >> k[i];
    for (int i = 0; i < n; i++)
    {
        dp1[i] = make_pair(1, -1);
        int mask1 = a[i] >> 10;
        int mask2 = a[i] % (1 << 10);
        for (int mask = 0; mask < (1 << 10); mask++)
        {
            int cnt = __builtin_popcount(mask & mask1);
            if (cnt <= k[i] && k[i] - cnt <= 10 && dp[mask][mask2][k[i] - cnt].first + 1 > dp1[i].first)
            {
                dp1[i].first = dp[mask][mask2][k[i] - cnt].first + 1;
                dp1[i].second = dp[mask][mask2][k[i] - cnt].second;
            }
        }
        for (int mask = 0; mask < (1 << 10); mask++) 
            dp[mask1][mask][__builtin_popcount(mask & mask2)] = max(dp[mask1][mask][__builtin_popcount(mask & mask2)], make_pair(dp1[i].first, i));
    }
    vector<int> ans;
    pair<int, int> ma = make_pair(0, 0);
    for (int i = 0; i < n; i++) ma = max(ma, make_pair(dp1[i].first, i));
    cout << ma.first << "\n";
    for (int i = 0; i < ma.first; i++)
    {
        ans.push_back(ma.second);
        ma.second = dp1[ma.second].second;
    }
    reverse(all(ans));
    for (int x : ans) cout << x + 1 << " ";
    cout << "\n";
}

int main() {
    sui;
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

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