Submission #673625

#	Time	Username	Problem	Language	Result	Execution time	Memory
673625		beedle	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	5721 ms	184324 KiB

subsequence

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <complex>
#include <assert.h>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define ld long long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 1000000007ll
#define INF 1e18
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast                                                                  \
    ios_base::sync_with_stdio (false);                                        \
    cin.tie (NULL);                                                           \
    cout.tie (NULL)
 
using namespace std;

signed main()
{
    fast;

    ll n;
    cin>>n;

    ll arr[n+1];
    rep(i,1,n)
    cin>>arr[i];

    ll k[n+1];
    rep(i,1,n)
    cin>>k[i];

    static pair <ll,ll> dp[1ll<<10][1ll<<10][11];   // seqlength, index
    ll maxseq[n+1];
    ll from[n+1];
    rep(i,1,n)
    maxseq[i]=1, from[i]=i;


    ll lhs=arr[1]&((1ll<<10)-1);
    ll rhs=arr[1]>>10;
    rep(other,0,(1ll<<10)-1)
    dp[lhs][other][__builtin_popcount(rhs&other)]={1,1};

    rep(i,2,n)
    {
        ll lhs=arr[i]&((1ll<<10)-1);
        ll rhs=arr[i]>>10;
        rep(prevlhs,0,(1ll<<10)-1)
        {
            ll req=k[i]-__builtin_popcount(prevlhs&lhs);
            if(req>=0 && req<=10)
            if(dp[prevlhs][rhs][req].ff+1>maxseq[i])
            maxseq[i]=dp[prevlhs][rhs][req].ff+1, from[i]=dp[prevlhs][rhs][req].ss;
        }
        rep(other,0,(1ll<<10)-1)
        dp[lhs][other][__builtin_popcount(rhs&other)]=max(dp[lhs][other][__builtin_popcount(rhs&other)],{maxseq[i],i});
    }

    ll curr;
    ll best=0;

    rep(i,1,n)
    if(maxseq[i]>best)
    best=maxseq[i], curr=i;

    cout<<best<<endl;
    vector <int> v;
    while(curr!=from[curr])
    {
        v.pb(curr);
        curr=from[curr];
    }
    v.pb(curr);
    reverse(all(v));
    for(auto x:v)
    cout<<x<<" ";

    return 0;
}

/*
4 
1 2 3 4 
10 0 1 0
*/

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

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:97:9: warning: 'curr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |     v.pb(curr);
      |     ~~~~^~~~~~

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