Submission #1098577

#TimeUsernameProblemLanguageResultExecution timeMemory
1098577vjudge1Longest beautiful sequence (IZhO17_subsequence)C++17
7 / 100
154 ms262144 KiB
#include <bits/stdc++.h>
using namespace std;

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
	long long n,  i, j, k, mx, mxi, ans1=0, ans2=0;
	cin >> n;
	for (i=1; i<=n; i++)
    {
        cin >> a[i];
    };
    for (i=1; i<=n; i++)
    {
        mx=mxi=0;
        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; mxi=dp[j][a[i]%(1LL<<10)][b[i]-k][1];};
        };
        trace[i]=mxi;
        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();};
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...