Submission #1050586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050586		handlename	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	1 ms	4700 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define float long double
const int MOD=1e9+7;
// const int MOD=998244353;
const int sqn=450;
const long double eps=1e-6;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
long long power(long long a,long long b,long long p=MOD){
    long long res=1;
    while (b>0){
        if (b%2==1) res=(res*a)%p;
        b/=2;
        a=(a*a)%p;
    }
    return res;
}
int n,arr[100001],brr[100001];
// idea 1: dp1[x] = LBS ending with x
// idea 2: dp2[i][k] = max length of LBS ending with x
// over all x such that bitcount(x&i)=k
// for idea 2, we get O(1) transitions
// but we then need to update O(M) states in dp2
// idea 1 has O(M) transition, O(1) affected states
// idea 2 has O(1) transition, O(M) affected states
int dp[1100][1100][11],from[1100][1100][11],prv[100001];
// main idea is to split X into its left and right bits
// lx is left bits, rx is right bits
// dp[i][j][k] = max legnth of LBS ending with x such that
// lx = i
// bitcount(rx&j) = k
// from just stores the last index of the LBS
void runtc(){
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>arr[i];
    }
    for (int i=1;i<=n;i++){
        cin>>brr[i];
    }
    pair<int,int> ans=mp(1,-1);
    memset(prv,-1,sizeof(prv));
    for (int id=1;id<=n;id++){
        int lx=arr[id]>>10;
        int rx=arr[id]%(1<<10);
        int lbs=1; //answer for id
        for (int i=0;i<(1<<10);i++){
            int rbits=brr[id]-__builtin_popcount(lx&i);
            if (rbits<0 || rbits>10) continue;
            if (dp[i][rx][rbits]+1>lbs){
                lbs=dp[i][rx][rbits]+1;
                prv[id]=from[i][rx][rbits];
            }
        }
        cout<<id<<' '<<lbs<<'\n';
        ans=max(ans,mp(lbs,id));
        for (int j=0;j<(1<<10);j++){
            int rbits=__builtin_popcount(rx&j);
            if (lbs>dp[lx][j][rbits]){
                dp[lx][j][rbits]=lbs;
                from[lx][j][rbits]=id;
            }
        }
    }
    vector<int> res;
    while (ans.second!=-1){
        res.pb(ans.second);
        ans.second=prv[ans.second];
    }
    reverse(res.begin(),res.end());
    cout<<res.size()<<'\n';
    for (auto i:res){
        cout<<i<<' ';
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("movie.in","r",stdin);
    // freopen("movie.out","w",stdout);
    //freopen("input1.in","r",stdin);
    // freopen("output1.out","w",stdout);
    //freopen("tower_rush_input.txt","r",stdin);
    //freopen("hackercup_output.txt","w",stdout);
    int tcs;
    // cin>>tcs;
    tcs=1;
    for (int i=1;i<=tcs;i++){
        // cout<<"Case #"<<i<<": ";
        runtc();
    }
}

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