Submission #162078

#	Time	Username	Problem	Language	Result	Execution time	Memory
162078		Alexa2001	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	19 ms	5240 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

const int ValM = (1<<10), Nmax = 1e5 + 5;

int n;
int A[Nmax], B[Nmax], best[ValM][ValM][11], bt[ValM * ValM], dp[Nmax], come[Nmax];

int main()
{
//	freopen("input", "r", stdin);
	cin.sync_with_stdio(false); cin.tie(0);

	cin >> n;
	int i, j;
	int best_end = 0;

	for(i=1; i<=n; ++i) cin >> A[i];
	for(i=1; i<=n; ++i) cin >> B[i];

	for(i=0; i<(1<<20); ++i)
		bt[i] = __builtin_popcount(i);

    for(i=1; i<=n; ++i)
	{
		int val1, val2;

        val1 = A[i] >> 10;
        val2 = A[i] & ((1<<10) - 1);

        dp[i] = 0;

        for(j=0; j<(1<<10); ++j)
		{
			int need = B[i] - bt[j & val1];
            if(need < 0) continue;

            if(dp[best[j][val2][need]] > dp[i])
                dp[i] = best[j][val2][need], come[i] = best[j][val2][need];
		}

        ++dp[i];

        for(j=0; j<(1<<10); ++j)
		{
            int now = bt[j & val2];
			if(dp[i] > dp[best[val1][j][now]])
                best[val1][j][now] = i;
		}

		if(dp[i] > dp[best_end]) best_end = i;
	}

	cout << dp[best_end] << '\n';

	vector<int> v;
    int pos = best_end;
    while(pos)
	{
		v.push_back(pos);
		pos = come[pos];
	}

    reverse(v.begin(), v.end());
    for(auto it : v) cout << it << ' ';

    return 0;
}

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