제출 #1098795

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098795		vjudge1	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4143 ms	29936 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
using lli = long long;
const int maxN = 2e6 + 5;
const int maxD = (1 << 10) + 5;
int f[maxN],n,a[maxN],k[maxN],tr[maxN];
int dp[11][maxD][maxD];
vector<int> q;
void input()
{
    cin >> n;
    for (int i = 1;i <= n;++i) cin >> a[i];
    for (int i = 1;i <= n;++i) cin >> k[i];
}
void solve()
{
    f[0] = 0;
    int res = 1;
    for (int i = 1;i <= n;++i)
    {
        f[i] = 1;
        int pre = a[i] / (1 << 10);
        int suf = a[i] % (1 << 10);
        for (int k0 = 0;k0 < 11;++k0)
        for (int j = 0;j < (1 << 10);++j)
            if (k0 + __builtin_popcountll(suf & j) == k[i] && f[dp[k0][pre][j]] + 1 > f[i])
            {
                f[i] = f[dp[k0][pre][j]] + 1;
                tr[i] = dp[k0][pre][j];
            }
        for (int j = 0;j < (1 << 10);++j)
            if (f[dp[__builtin_popcountll(j & pre)][j][suf]] < f[i]) dp[__builtin_popcountll(j & pre)][j][suf] = i;
        if (f[res] < f[i]) res = i;
    }
    cout << f[res] << "\n";
    do
    {
        q.push_back(res);
        res = tr[res];
    }
    while (res != 0);
    reverse(q.begin(),q.end());
    for (int v : q) cout << v << " ";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("A.inp","r",stdin);
//    freopen("A.out","w",stdout);
    input();
    solve();
}

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