Submission #653051

#	Time	Username	Problem	Language	Result	Execution time	Memory
653051		MilosMilutinovic	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3560 ms	81080 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
const int N=100050;
const int M=(1<<10);
int n,a[N],k[N];
pair<int,int> dp[N],mx[22][M][M];
void ckmax(pair<int,int>&a,pair<int,int> b){a=max(a,b);}
int main(){
    scanf("%i",&n);
    for(int i=1;i<=n;i++)scanf("%i",&a[i]);
    for(int i=1;i<=n;i++)scanf("%i",&k[i]);
    for(int i=1;i<=n;i++){
        for(int f=0;f<(1<<10);f++){
            int c=__builtin_popcount(a[i]&f);
            if(k[i]<c)continue;
            pair<int,int> v=mx[k[i]-c][f][a[i]>>10];
            v.first+=1;
            ckmax(dp[i],v);
        }
        for(int f=0;f<(1<<10);f++){
            int x=(a[i]>>10);
            int c=__builtin_popcount(x&f);
            ckmax(mx[c][a[i]&((1<<10)-1)][f],{dp[i].first,i});
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,dp[i].first);
    printf("%i\n",ans);
    for(int i=1;i<=n;i++)if(dp[i].first==ans){
        vector<int> ids;
        int x=i;
        while(x>0){
            ids.push_back(x);
            x=dp[x].second;
        }
        reverse(ids.begin(),ids.end());
        for(int j=0;j<(int)ids.size();j++)printf("%i ",ids[j]);
        break;
    }
    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
subsequence.cpp:10:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     for(int i=1;i<=n;i++)scanf("%i",&a[i]);
      |                          ~~~~~^~~~~~~~~~~~
subsequence.cpp:11:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     for(int i=1;i<=n;i++)scanf("%i",&k[i]);
      |                          ~~~~~^~~~~~~~~~~~

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