Submission #680508

#	Time	Username	Problem	Language	Result	Execution time	Memory
680508		ReLice	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	4300 ms	94976 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
#define pb push_back
#define sz size()
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll N = 1e5+10;
const ll mod=1e9+7;
const ll inf=1e10;
ll n,m;
ll dp[N],a[1024][1024][11];
ll v[N],v2[N],p[N];
ll cnt(ll x){
	return __builtin_popcount(x);
}
void solve(){
    ll b,i,j,mx=-1,mn=mod,ans=1,sum=1,c=0,l,r;
    cin>>n;
    for(i=1;i<=n;i++)cin>>v[i];
    for(i=1;i<=n;i++)cin>>v2[i];
    for(i=1;i<=n;i++){
        l=(v[i]>>10);
        r=v[i]&((1<<10)-1);
        ans=0;
        for(j=0;j<(1<<10);j++){
            c=v2[i]-cnt(j&r);
            if(c<0 || c>10) continue;
            if(dp[ans]<dp[a[l][j][c]]) ans=a[l][j][c];
        }
        dp[i]=dp[ans]+1;
        p[i]=ans;
        for(j=0;j<(1<<10);j++){
            c=cnt(j&l);
            if(dp[i]>dp[a[j][r][c]]) a[j][r][c]=i;
        }

    }
    for(i=1;i<=n;i++){
        if(dp[i]>dp[sum])sum=i;
    }
    vector <ll> res;
    while(sum!=0){
        res.pb(sum);
        sum=p[sum];
    }
    cout<<res.sz<<endl;
    reverse(res.begin(),res.end());
    for(auto i : res) cout<<i<<' ';

}
main(){
    //fre("");
    //start();
    ll t=1;
    //cin>>t;
    while(t--)solve();

}

Compilation message (stderr)

subsequence.cpp: In function 'void solve()':
subsequence.cpp:25:8: warning: unused variable 'b' [-Wunused-variable]
   25 |     ll b,i,j,mx=-1,mn=mod,ans=1,sum=1,c=0,l,r;
      |        ^
subsequence.cpp:25:14: warning: unused variable 'mx' [-Wunused-variable]
   25 |     ll b,i,j,mx=-1,mn=mod,ans=1,sum=1,c=0,l,r;
      |              ^~
subsequence.cpp:25:20: warning: unused variable 'mn' [-Wunused-variable]
   25 |     ll b,i,j,mx=-1,mn=mod,ans=1,sum=1,c=0,l,r;
      |                    ^~
subsequence.cpp: At global scope:
subsequence.cpp:59:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   59 | main(){
      | ^~~~

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