Submission #1098595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098595		vjudge1	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	2 ms	3164 KiB

subsequence

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

long long a[100005], b[100005], trace[100005], dp[1030][1030][11][2];
stack<long long> st;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
	long long n,  i, j, k, mx, ans1=0, ans2=0;
	cin >> n;
	for (i=1; i<=n; i++)
    {
        cin >> a[i];
    };
    for (i=1; i<=n; i++)
    {
        mx=1;
        cin >> b[i];
        for (j=0; j<(1LL<<10); j++)
        {
            k=__builtin_popcount(j&(a[i]>>10));
            if (k>b[i]) {continue;};
            if (dp[j][a[i]%(1LL<<10)][b[i]-k][0]+1>mx) {mx=dp[j][a[i]%(1LL<<10)][b[i]-k][0]+1; trace[i]=dp[j][a[i]%(1LL<<10)][b[i]-k][1];};
        };
        for (j=0; j<(1LL<<10); j++)
        {
            k=__builtin_popcount(j&(a[i]%(1LL<<10)));
            if (mx>dp[a[i]>>10][j][k][0]) {dp[a[i]>>10][j][k][0]=mx; dp[a[i]>>10][j][k][1]=i;};
        };
        if (mx>ans1) {ans1=mx; ans2=i;};
    };
    cout << ans1 << "\n";
    while (ans2>0) {st.push(ans2); ans2=trace[ans2];};
    while (!st.empty()) {cout << st.top() << " "; st.pop();};
}

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