Submission #170155

#	Time	Username	Problem	Language	Result	Execution time	Memory
170155		nvmdava	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4405 ms	97712 KiB

subsequence

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,avx2")
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define N 100005
#define LIM 1024
int a[N], k[N], ans[N], f[N];
int bit[1050000];

int dp[LIM][LIM][11], fr[LIM][LIM][11];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, mxid = 1;
    cin>>n;
    for(int i = 1; i <= 1048576; ++i)
        bit[i] = __builtin_popcount(i);

    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 <= n; ++i){
        ans[i] = 1;
        int l = a[i] >> 10;
        int r = a[i] - (l << 10);

        for(int j = 0; j < LIM; ++j){
            int q = k[i] - bit[l & j];
            if(q < 0 || q > 10) continue;
            if(ans[i] <= dp[j][r][q])
                ans[i] = dp[j][r][q] + 1, f[i] = fr[j][r][q];
        }
        if(ans[i] > ans[mxid])
            mxid = i;
        for(int j = 0; j < LIM; ++j){
            int q = bit[j & r];
            if(dp[l][j][q] < ans[i])
                dp[l][j][q] = ans[i], fr[l][j][q] = i;
        }
    }

    cout<<ans[mxid]<<'\n';

    vector<int> v;

    while(mxid){
        v.push_back(mxid);
        mxid = f[mxid];
    }
    reverse(v.begin(), v.end());
    for(auto& x : v)
        cout<<x<<' ';
}

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