제출 #665002

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
665002		finn__	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	6049 ms	1880 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n;
    cin >> n;

    if (n == 1)
    {
        cout << 1 << '\n'
             << 1 << '\n';
        return 0;
    }

    vector<unsigned> a(n), k(n);
    for (unsigned &x : a)
        cin >> x;
    for (unsigned &x : k)
        cin >> x;

    vector<unsigned> dp(n, 1), pre(n, UINT_MAX);
    unsigned max_seq = 0, max_end = UINT_MAX;

    for (size_t i = 1; i < n; i++)
    {
        for (size_t j = 0; j < i; j++)
        {
            if (__builtin_popcount(a[j] & a[i]) == k[i] && dp[j] + 1 > dp[i])
            {
                dp[i] = dp[j] + 1;
                pre[i] = j;
            }
        }

        if (dp[i] > max_seq)
        {
            max_seq = dp[i];
            max_end = i;
        }
    }

    cout << max_seq << '\n';

    unsigned i = max_end;
    vector<unsigned> seq;

    while (i != UINT_MAX)
    {
        seq.push_back(i + 1);
        i = pre[i];
    }
    for (auto it = seq.rbegin(); it != seq.rend(); it++)
        cout << *it << ' ';
    cout << '\n';
}

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