Submission #863966

#	Time	Username	Problem	Language	Result	Execution time	Memory
863966		Requiem	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3198 ms	193892 KiB

subsequence

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define endl "\n"
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define pi 3.14159265359
#define TASKNAME "subsequence"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; } 
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; } 
using namespace std; 
typedef pair<int,int> ii; 
typedef pair<int,ii> iii; 
typedef vector<int> vi; 
const int MAXN = 2e5 + 9;
int a[MAXN],k[MAXN],n;
int bc[1025][1025];
struct data{
    int len=0,end=0;
}dp[1025][1025][11];
const int B = 10;
main() 
{ 
    fast; 
    // freopen(TASKNAME".inp","r",stdin); 
    // freopen(TASKNAME".out","w",stdout);
    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=0;i<1024;i++){
        for(int j=0;j<1024;j++){
            bc[i][j] = __builtin_popcount(i&j);
        }
    }
    vector<int> prv(n+1);
    int ans = 0;
    iota(prv.begin(),prv.end(),0);
    int best = 0;
    for(int i=1;i<=n;i++){
        int l = a[i] >> B;
        int r = a[i] % (1<<B);
        int lbs = 1;
        for(int j=0;j<(1<<B);j++){
            int needed = k[i] - bc[l][j];
            if (needed >= 0 and needed <= B and dp[j][r][needed].len + 1 > lbs){
                lbs = dp[j][r][k[i]-bc[l][j]].len + 1;
                prv[i] = dp[j][r][k[i]-bc[l][j]].end;
            }
        }
        if (ans < lbs){
            ans = lbs;
            best = i;
        }

        for(int j=0;j<(1<<B);j++){
            if (lbs > dp[l][j][bc[j][r]].len){
                dp[l][j][bc[j][r]] = {lbs,i};
            }
        }
    }
    cout<<ans<<endl;
    vector<int> res;
    res.pb(best);
    // for(int i=1;i<=n;i++){
    //     cout<<prv[i]<<' ';
    // }
    // cout<<endl;
    while (prv[best] != best){
        best = prv[best];
        res.pb(best);
    }
    for(int i=res.size()-1;i>=0;i--){
        cout<<res[i]<<' ';
    }
    cout<<endl;


}

Compilation message (stderr)

subsequence.cpp:28:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   28 | main()
      | ^~~~

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