제출 #507011

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

subsequence

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
void db() {cout << endl;}
template <typename T, typename ...U> void db(T a, U ...b) {cout << a << ' ', db(b...);}
#ifdef Cloud
#define file freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define file ios::sync_with_stdio(false); cin.tie(0)
#endif
#define pii pair<int, int>
const int inf = 1e9, N = 120, _N = 501, mod = 998244353;
pair<int, int> p[_N][N]{};
pii get(pii u){
    return p[u.fi][u.se] = p[u.fi][u.se] == u ? u : get(p[u.fi][u.se]);
}
void merge(pii a, pii b){
    b = get(b);
    p[a.fi][a.se] = b;
}
int main(){
    
    file;
    /*
    int n;
    cin >> n;
    int a[n], tot = 0;
    for (int &i : a) cin >> i, tot += i;
    if (tot % 2) return cout << 0 << '\n', 0;
    int cnt[N]{};
    bool dp[N]{}, can[_N][N]{};
    for (int i = 0; i < N; i++) p[n][i] = {n, i};
    for (int i = n - 1; i >= 0; i--){
        for (int j = 0; j < N; j++) p[i][j] = p[i + 1][j];
        for (int j = a[i]; j < N; j++) merge(p[i][j], p[i + 1][j - a[i]]);
    }
    dp[0] = 1;
    //db(p[3][8]);
    for (int i = 0; i < n; i++){
        bool can[N]{};
        for (int j = 0; j < N; j++) if (dp[j]) {
            auto u = get(i + 1, j);
            can[u.fi][u.se] = 1;
        }
        for (int j = 0; j < N; j++) {
            auto u = get(i + 1, j);
            if (can[u.fi][u.se] and j * 2 >= tot - a[i]){
                db(i, j, j * 2 - tot + a[i]);
                cnt[j * 2 - tot + a[i]]++;
            }
        }
        for (int j = N - 1; j >= a[i]; j--) dp[j] |= dp[j - a[i]];
    }
    if (!dp[tot / 2]) return cout << 0 << '\n', 0;
    vector<int> ans;
    for (int i = 1; i < N; i++) if (cnt[i] == n) ans.push_back(i);
    cout << ans.size() << '\n';
    for (int i : ans) cout << i << ' ';
    */
    int n;
    cin >> n;
    int a[n], k[n], dp[(1 << 8)]{}, par[n], ma[(1 << 8)], ans = 0, tar = 0;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> k[i];
    for (int i = 0; i < n; i++){
        int tmp = 1;
        par[i] = -1;
        if (i) for (int j = 0; j < (1 << 8); j++) if (__builtin_popcount(a[i] & j) == k[i]){
            if (tmp < dp[j] + 1) tmp = dp[j] + 1, par[i] = ma[j];
        }
        if (tmp > dp[a[i]]) dp[a[i]] = tmp, ma[a[i]] = i; 
        if (tmp > ans) ans = tmp, tar = i;
    }
    cout << ans <<'\n';
    vector<int> v;
    for (int i = tar; i >= 0; i = par[i]) v.push_back(i);
    reverse(v.begin(), v.end());
    for (int i : v) cout << i + 1 << ' ';
}

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