Submission #1333250

#TimeUsernameProblemLanguageResultExecution timeMemory
1333250fatelessLongest beautiful sequence (IZhO17_subsequence)C++20
23 / 100
6093 ms3068 KiB
// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define now chrono::steady_clock::now().time_since_epoch().count()
#define speedup cin.tie(0)->sync_with_stdio(0)
#define bitcount __builtin_popcount
#define all(x) begin(x), end(x)
#define int long long
#define pb push_back
#define arr array
#define vc vector

using ll = long long;
const int inf = 1e18, N = 1e5 + 1;
static int a[N], b[N], dp[N], p[N];
template <class T> bool chmax(T &a, T b) {if (a < b) {a = b; return 1;} return 0;}

inline void solve () {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    int ans = 0, st = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        for (int j = 1; j < i; j++) 
            if (bitcount(a[i] & a[j]) == b[i])
                if (chmax(dp[i], dp[j] + 1)) p[i] = j;
        
        if (chmax(ans, dp[i])) st = i;
    }

    cout << ans << '\n';
    vc<int> ord;
    while (st) {
        ord.pb(st);
        st = p[st];
    }

    reverse(all(ord));
    for (int x : ord) cout << x << ' ';
}

signed main() {
    speedup;
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...