Submission #524098

#	Time	Username	Problem	Language	Result	Execution time	Memory
524098		Nursik	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	2007 ms	55200 KiB

subsequence

#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define ld long double
#define f first
#define s second
#define mp make_pair

const ll maxn = 2e6 + 100, maxm = 11,  maxk = (1 << 10);
const ll inf = 1000000000, mod = inf + 7, mod2 = 998244353;
const ll pa = 31, block = 400;

using namespace std;

int n;
int a[maxn], k[maxn], len[maxn], last[maxn], dp[maxk][maxk][maxm], cnt[maxn];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i){
        cin >> k[i];
    }
    for (int i = 1; i <= maxn - 1; ++i){
        cnt[i] = __builtin_popcount(i);
    }
    for (int i = 1; i <= n; ++i){
        int f = 0, s = 0;
        for (int j = 0; j < 10; ++j){
            if ((1 << j) & a[i]){
                f |= (1 << j);
            }
            if ((1 << (j + 10)) & a[i]){
                s |= (1 << j);
            }
        }
        len[i] = 1;
        for (int j = 0; j < maxk; ++j){
            int need = k[i] - cnt[j & f];
            if (need >= 0 && need < maxm){
                int pos = dp[j][s][need];
                if (pos > 0 && len[pos] + 1 > len[i]){
                    len[i] = len[pos] + 1;
                    last[i] = pos;
                }
            }
        }
        for (int j = 0; j < maxk; ++j){
            int x = cnt[j & s];
            int ind = dp[f][j][x];
            if (len[ind] < len[i]){
                dp[f][j][x] = i;
            }
        }
    }
    int pos = 0;
    for (int i = 1; i <= n; ++i){
        if (len[pos] < len[i]){
            pos = i;
        }
    }
    vector<int> v;
    while (pos > 0){
        v.pb(pos);
        pos = last[pos];
    }
    cout << v.size() << '\n';
    reverse(v.begin(), v.end());
    for (auto it : v){
        cout << it << " ";
    }
}

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