제출 #1271988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271988		LucasLe	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	8 ms	1852 KiB

subsequence

#include <bits/stdc++.h>
 
#define fi first
#define se second
#define ld long double
#define pii std::pair<int, int>
#define piii std::pair<pii, pii>

#define rep(i,a) for (int i = 0; i < a; ++i)
#define per(i,a) for (int i = a - 1; i >= 0; --i)

const int maxn = 1e5;

int N;
int a[maxn + 5], k[maxn + 5];

int trace[maxn + 5];
pii f[1025][1025][11];

void solve() {
    std::cin >> N;
    for (int i = 1; i <= N; ++i)
        std::cin >> a[i];
    for (int i = 1; i <= N; ++i)
        std::cin >> k[i];

    int ans = 0, pos;
    for (int i = 1; i <= N; ++i) {
        int maskL = (a[i] >> 10);
        int maskR = (a[i] & ((1 << 10) - 1));

        int res = 0;
        for (int mask = 0; mask < (1 << 10); ++mask) {
            int cnt = __builtin_popcount(maskL & mask);
            if (cnt > k[i])
                continue;
            if (f[mask][maskR][k[i] - cnt].fi + 1 > res) {
                res = f[mask][maskR][k[i] - cnt].fi + 1;
                trace[i] = f[mask][maskR][k[i] - cnt].se;
            }
        }

        for (int mask = 0; mask < (1 << 10); ++mask) {
            int cnt = __builtin_popcount(maskR & mask);
            if (res > f[maskL][mask][cnt].fi) {
                f[maskL][mask][cnt] = {res, i};
            }
        }

        if (res > ans) {
            ans = res;
            pos = i;
        }
    }

    std::vector<int> vec;
    while (pos) {
        vec.push_back(pos);
        pos = trace[pos];
    }
    reverse(vec.begin(), vec.end());

    std::cout << ans << '\n';
    for (int x : vec)
        std::cout << x << ' ';


}

int main() {
    // std::freopen("input.txt", "r", stdin);
    // std::freopen("palin.inp", "r", stdin);
    // std::freopen("sushi.out", "w", stdout);
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);

    int T = 1; 
    // std::cin >> T;
    while (T--)
        solve();

}

// 14 / 2 (87.5% Rate)

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