제출 #1171199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171199		paulxaxa	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	109 ms	1608 KiB

subsequence

#include <bits/stdc++.h>

#define NMAX 100000
#define LOG 19

#define ll long long int
#define BASE 1024

#define MOD 1000000009


using namespace std;

ifstream fin("cod.in");
ofstream fout("cod.out");

int a[NMAX+1],k[NMAX+1];

int n;
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin >> k[i];
    }
    if(n<=5000)
    {
        vector<pair<int,int>> dp(n+1);
        for(int i=1;i<=n;i++)
        {
            dp[i].first = 1;
            for(int j=i-1;j>=1;j--)
            {
                if(__builtin_popcount(a[j] & a[i]) == k[i])
                {
                    if(dp[i].first < dp[j].first + 1)
                    {
                        dp[i] = {dp[j].first + 1,j};
                    }
                }
            }
        }
        int mx=0;
        for(int i=1;i<=n;i++)
        {
            if(dp[mx].first < dp[i].first)
            {
                mx=i;
            }
        }
        vector<int> res;
        while(mx)
        {
            res.push_back(mx);
            mx = dp[mx].second;
        }
        cout << res.size() << '\n';
        reverse(res.begin(),res.end());
        for(int i : res)
        {
            cout << i << " ";
        }
    }
    else
    {
        vector<pair<int,int>> dp(1<<8 , {0,0});
        vector<int> prev(n+1);

        for(int i=1;i<=n;i++)
        {
            int mx = 1;
            prev[i] = 0;
            for(int j=0;j<(1<<8);j++)
            {
                if(__builtin_popcount(j & a[i]) == k[i] && dp[j].first + 1 > mx)
                {
                    mx = dp[j].first + 1;
                    prev[i] = dp[j].second;
                }
            }
            if(mx > dp[a[i]].first)
            {
                dp[a[i]] = {mx,i};
            }
        }
        int mx=0;
        for(int i=0;i<(1<<8);i++)
        {
            if(dp[mx].first < dp[i].first)
            {
                mx = i;
            }
        }
        vector<int> res;
        mx = dp[mx].second;
        while(mx)
        {
            res.push_back(mx);
            mx = prev[mx];
        }
        reverse(res.begin(),res.end());
        cout << res.size() << '\n';
        for(int i : res)
        {
            cout << i << " ";
        }

    }
}

//5 3 5 3 5
//10 1 20 1 20

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