Submission #156286

#	Time	Username	Problem	Language	Result	Execution time	Memory
156286		andrew	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	6056 ms	174384 KiB

subsequence

#include <bits/stdc++.h>

//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)

using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = 1123456;
const int N = 1e5 + 3;
const int M = pw(10);
const int inf = 3e18;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

template <typename T> void vout(T s){cout << s << endl;exit(0);}

int f[1025][1025][21], f1[1025][1025][21];
int a[N], k[N], dp[N], pr[N];

void vivod(int x){
    if(!x)return;
    vivod(pr[x]);
    cout << x << "\n";
}

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

    int n;
    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 <= n; i++){
        dp[i] = 1;
        int F = (M - 1) & a[i], S = a[i] >> 10;
        for(int j = 0; j < M; j++){
            int K = k[i] - __builtin_popcount(j & S);
            if(K >= 0){
                if(dp[i] < f[F][j][K] + 1){
                    dp[i] = f[F][j][K] + 1;
                    pr[i] = f1[F][j][K];
                }
            }
        }

        for(int j = 0; j < M; j++){
            int K = __builtin_popcount(F & j);
            if(dp[i] > f[j][S][K]){
                f[j][S][K] = dp[i];
                f1[j][S][__builtin_popcount(F & j)] = i;
            }
        }
    }

    int Mx = *max_element(dp + 1, dp + n + 1);

    cout << Mx << "\n";

    for(int i = 1; i <= n; i++)if(dp[i] == Mx){
        int x = i;
        vivod(x);
        return 0;

    }

    return 0;
}

Compilation message (stderr)

subsequence.cpp:24:17: warning: overflow in implicit constant conversion [-Woverflow]
 const int inf = 3e18;
                 ^~~~

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