제출 #1171273

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171273		paulxaxa	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	32 ms	14152 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 l[1<<20],r[1<<20];
int bc[1<<10][1<<10];

pair<int,int> dp[1<<10][1<<10][10+1];
int prv[NMAX+1];

int n;

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

int main()
{
    for(int i=0;i<(1<<10);i++)
    {
        for(int j=0;j<(1<<10);j++)
        {
            bc[i][j] = __builtin_popcount(i&j);
        }
    }
    for(int i=0;i<(1<<20);i++)
    {
        l[i] = i >> 10;
        r[i] = i & ((1<<10)-1);
    }

    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++)
    {
        int mx=0;
        for(int lx = 0;lx<(1<<10);lx++)
        {
            int t = k[i] - bc[lx][l[a[i]]];
            if(t >= 0 && dp[lx][r[a[i]]][t].first + 1 > mx )
            {
                mx  = dp[lx][r[a[i]]][t].first + 1;
                prv[i] = dp[lx][r[a[i]]][t].second;
            }
        }

        for(int rx=0;rx < (1<<10);rx++)
        {
            int t = bc[rx][r[a[i]]];
            if(dp[l[a[i]]][rx][t].first < mx)
            {
                dp[l[a[i]]][rx][t].first = mx;
                dp[l[a[i]]][rx][t].second = i;
            }
        }
    }
    int mx=0,j=0;
    for(int lx=0;lx<(1<<10);lx++)
    {
        for(int rx=0;rx<(1<<10);rx++)
        {
            for(int t=0;t<=10;t++)
            {
                if(mx < dp[lx][rx][t].first)
                {
                    mx = dp[lx][rx][t].first;
                    j = dp[lx][rx][t].second;
                }
            }
        }
    }
    vector<int> res;
    while(j)
    {
        res.push_back(j);
        j = prv[j];
    }
    cout << res.size() << "\n";
    reverse(res.begin(),res.end());
    for(int i : res)
    {
        cout << i << " ";
    }

}

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

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