제출 #807881

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

subsequence

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int N = 1e5 + 5;

int a[N], k[N], dp1[N], ans[N];
pair<int, int> dp2[N];
vector<int> v;

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> k[i];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < (1 << 8); j++) {
                if (__builtin_popcount(a[i] & j) != k[i] or dp2[a[i]].fi > dp2[j].fi) continue;
                dp2[a[i]].fi = dp2[j].fi + 1, ans[i] = dp2[j].se, dp2[a[i]].se = i;
            }
            if (dp2[a[i]].fi == 0) dp2[a[i]].fi = 1, dp2[a[i]].se = i;
        }
        int id = 0;
        for (int i = 1; i <= n; i++) if (dp2[a[i]].fi > dp2[a[id]].fi) id = i;
        cout << dp2[a[id]].fi << "\n";
        while (id != 0) {
            v.push_back(id);
            id = ans[id];
        }
        reverse(v.begin(), v.end());
        for (auto x : v) cout << x << " ";
        cout << "\n";
}  

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