제출 #677800

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
677800		Mher	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	202 ms	4176 KiB

subsequence

#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <queue>

using namespace std;

const int N = 5003, mod = 1e9 + 7;

int n;
int a[N], k[N];
vector<int> pv[N];
int dp[N], pr[N];

int cnt(int x)
{
    int res = 0;
    while (x)
    {
        res += x & 1;
        x >>= 1;
    }
    return res;
}

void solve()
{
    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++)
    {
        pv[i].push_back(0);
        for (int j = i - 1; j > 0; j--)
        {
            if (cnt(a[i] & a[j]) == k[i])
            {
                pv[i].push_back(j);
            }
        }
    }
    int ans = 0, ai = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int p : pv[i])
        {
            if (dp[p] + 1 > dp[i])
            {
                dp[i] = dp[p] + 1;
                pr[i] = p;
            }
        }
        if (ans < dp[i])
        {
            ans = dp[i];
            ai = i;
        }
    }
    vector<int> av;
    while (ai != 0)
    {
        av.push_back(ai);
        ai = pr[ai];
    }
    cout << ans << endl;
    for (int i = ans - 1; i >= 0; i--)
        cout << av[i] << ' ';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
    return 0;
}

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