Submission #234823

#	Time	Username	Problem	Language	Result	Execution time	Memory
234823		muhammad_hokimiyon	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3131 ms	92816 KiB

subsequence

#include <bits/stdc++.h>

//#pragma GCC optimize("Ofast")

#define fi first
#define se second
#define ll long long
#define dl double long

using namespace std;

const int NN = 2e6 + 7;
const int N = 1e6 + 7;
const int M = 22;
const int mod = 998244353;
const ll inf = 1e18 + 7;
const dl rf = 1e-14;
const int B = sqrt(N);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
int a[N];
int k[N];
int c[N];
pair < int , int > dp[N];
pair < int , int > d[(1 << 10)][(1 << 10)][11];

void solve1()
{
    cin >> n;
    pair < int , int > ans = {0 , 0};
    for( int i = 1; i <= n; i++ )cin >> a[i];
    for( int i = 1; i <= n; i++ )cin >> k[i];
    for( int i = 0; i < (1 << 10); i++ )c[i] = __builtin_popcount(i);
    for( int i = 1; i <= n; i++ ){
        dp[i] = {1 , 0};
        int h1 = (a[i] >> 10);
        int h2 = (a[i] & ((1 << 10) - 1));
        for( int j = 0; j < (1 << 10); j++ ){
            int f = c[(h2 & j)];
            if( k[i] - f >= 0 && k[i] - f <= 10 ){
                dp[i] = max( make_pair(d[j][h1][k[i] - f].fi + 1 , d[j][h1][k[i] - f].se) , dp[i] );
            }
        }
        for( int j = 0; j < (1 << 10); j++ ){
            int f = c[(h1 & j)];
            d[h2][j][f] = max( d[h2][j][f] , make_pair(dp[i].fi , i) );
        }
        ans = max( ans , {dp[i].fi , i} );
    }
    cout << ans.fi << "\n";
    vector < int > res;
    while( ans.se != 0 ){
        res.push_back(ans.se);
        ans.se = dp[ans.se].se;
    }
    assert( ans.fi == (int)res.size() );
    reverse( res.begin() , res.end() );
    for( auto x : res )cout << x << " ";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen( "input.txt" , "r" , stdin );
    //freopen( "output.txt" , "w" , stdout );

    int cghf = 1;//cin >> cghf;
    while( cghf-- ){
        solve1();
    }
}

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