Submission #1035767

#TimeUsernameProblemLanguageResultExecution timeMemory
1035767adaawfLongest beautiful sequence (IZhO17_subsequence)C++17
100 / 100
3731 ms179072 KiB
#include <iostream>
#include <vector>
using namespace std;
pair<int, int> f[1105][1105][21];
int g[100005], a[100005], b[100005];
int check(int x, int y) {
    x &= y;
    return __builtin_popcount(x);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, ma = 0, h = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    for (int i = 1; i <= n; i++) {
        int res = 1, k = 0, c = 0, d = 0;
        for (int j = 9; j >= 0; j--) {
            if (a[i] & (1 << j)) {
                c += (1 << j);
            }
        }
        for (int j = 9; j >= 0; j--) {
            if (a[i] & (1 << (j + 10))) {
                d += (1 << j);
            }
        }
        for (int j = 0; j < 1024; j++) {
            int h = b[i] - check(d, j);
            if (h < 0) continue;
            if (res < f[j][c][h].first + 1) {
                res = f[j][c][h].first + 1;
                k = f[j][c][h].second;
            }
        }
        g[i] = k;
        for (int j = 0; j < 1024; j++) {
            if (f[d][j][check(c, j)].first < res) {
                f[d][j][check(c, j)] = {res, i};
            }
        }
        if (ma < res) {
            ma = res;
            h = i;
        }
    }
    vector<int> v;
    while (h) {
        v.push_back(h);
        h = g[h];
    }
    cout << v.size() << '\n';
    for (int i = v.size() - 1; i >= 0; i--) cout << v[i] << " ";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...