Submission #633938

#	Time	Username	Problem	Language	Result	Execution time	Memory
633938		tht2005	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2973 ms	93420 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

int rd() {
    bool neg = 0; char c = getchar(); for(; c < '0' || c > '9'; c = getchar()) if(c == '-') neg = !neg;
    int n = 0; while('0' <= c && c <= '9') n = (n << 3) + (n << 1) + c - '0', c = getchar();
    return neg ? -n : n;
}
void wr(int n) {
    static char o[11];
    if(n < 0) putchar('-'), n = -n;
    int i = 0; do o[i++] = n % 10 + '0'; while(n /= 10);
    while(i--) putchar(o[i]);
}

inline bool ckmax(int& a, int b) {
    return (a < b) ? (a = b), 1 : 0;
}

#define N 100005

int a[N], trc[N], k[N], f[1 << 10][1 << 10][11], f2[1 << 10][1 << 10][11], g[N];

int main() {
    int n = rd();
    for(int i = 0; i < n; ++i) {
        a[i] = rd();
    }
    for(int i = 0; i < n; ++i) {
        k[i] = rd();
    }
    int res = 0, pos;
    for(int i = 0, l, r; i < n; ++i) {
        l = a[i] >> 10;
        r = a[i] & ((1 << 10) - 1);
        g[i] = 1;
        if(i) {
            for(int t = 1 << 10, cur; t--; ) {
                cur = __builtin_popcount(l & t);
                if(cur <= k[i] && k[i] - cur < 11) {
                    if(ckmax(g[i], f[t][r][k[i] - cur] + 1)) {
                        trc[i] = f2[t][r][k[i] - cur];
                    }
                }
            }
        }
        if(ckmax(res, g[i])) {
            pos = i;
        }
        for(int t = 1 << 10; t--; ) {
            if(ckmax(f[l][t][__builtin_popcount(r & t)], g[i])) {
                f2[l][t][__builtin_popcount(r & t)] = i;
            }
        }
    }
    vector<int> seq;
    while(1) {
        seq.push_back(pos);
        if(g[pos] == 1) {
            break;
        }
        pos = trc[pos];
    }
    wr(res);
    putchar('\n');
    for(int i = res; i--; ) {
        wr(seq[i] + 1);
        putchar(' ');
    }
    return 0;
}

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