Submission #1035767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035767		adaawf	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3731 ms	179072 KiB

subsequence

#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] << " ";
}

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