제출 #475053

#제출 시각아이디문제언어결과실행 시간메모리
475053TheScrasseLongest beautiful sequence (IZhO17_subsequence)C++17
0 / 100
7 ms1740 KiB
#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (int)1e9
#define mod 998244353
#define maxn 100010
#define maxb 1024
#define maxp 11

int i, i1, j, k, k1, t, n, m, flag[10], a[maxn], b[maxn];
int mk1, mk2, mk3, cr, pr[maxn];
array<int, 2> dp[maxb][maxb][maxp], res;
array<int, 5> rs;
vector<int> rsv;

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

    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (i = 1; i <= n; i++) {
        cin >> b[i];
    }

    for (i = 1; i <= n; i++) {
        mk1 = (a[i] >> 10); mk2 = a[i] - (1 << 10) * mk1;

        rs = {-1, 0};
        for (mk3 = 0; mk3 < (1 << 10); mk3++) {
            m = b[i] - __builtin_popcount(a[i] & mk3);
            if (m < 0) continue;
            rs = max(rs, {dp[mk3][mk2][m][0] + 1, dp[mk3][mk2][m][1], mk3, mk2, m});
        }
        res = max(res, {rs[0], i});

        for (mk3 = 0; mk3 < (1 << 10); mk3++) {
            m = __builtin_popcount(a[i] & mk3);
            if (rs[0] >= dp[mk1][mk3][m][0]) {
                dp[mk1][mk3][m] = {rs[0], i}; pr[i] = rs[1];
            }
        }
    }

    cout << res[0] << nl;
    cr = res[1];
    while (cr != 0) {
        rsv.pb(cr); cr = pr[cr];
    }

    reverse(rsv.begin(), rsv.end());
    for (auto u : rsv) cout << u << ' ';
    cout << nl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...