제출 #173018

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
173018		juggernaut	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	166 ms	20656 KiB

subsequence

//Just try and the idea will come!
#include<bits/stdc++.h>
#define int long long int
using namespace std;
int n,i,a[100001],k[100001],dp[100001],j,path[100001],mx,ind,m[(1ll<<20)],pos[(1ll<<20)];
vector<int>ans;
main(){
    scanf("%lld",&n);
    for(i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(i=1;i<=n;i++)scanf("%lld",&k[i]),dp[i]=1;
    if(n<=5000){
        for(i=1;i<=n;i++){
        for(j=1;j<i;j++)
            if(__builtin_popcount(a[i]&a[j])==k[i]&&dp[j]+1>dp[i]){
                dp[i]=dp[j]+1;
                path[i]=j;
            }
        if(dp[i]>mx){
            mx=dp[i];
            ind=i;
        }
    }
    do{
        ans.push_back(ind);
        ind=path[ind];
    }while(ind!=0);
    reverse(ans.begin(),ans.end());
    printf("%lld\n",(int)(ans.size()));
    for(int res:ans)printf("%lld ",res);
    return 0;
    }
    for(i=1;i<=n;i++){
        for(j=0;j<256;j++)
            if(__builtin_popcount(a[i]&j)==k[i]&&m[j]+1>dp[i]){
                dp[i]=m[j]+1;
                path[i]=pos[j];
            }
        if(dp[i]>m[a[i]]){
            m[a[i]]=dp[i];
            pos[a[i]]=i;
        }
        if(dp[i]>mx){
            mx=dp[i];
            ind=i;
        }
    }
    do{
        ans.push_back(ind);
        ind=path[ind];
    }while(ind!=0);
    reverse(ans.begin(),ans.end());
    printf("%lld\n",(int)(ans.size()));
    for(int res:ans)printf("%lld ",res);
}

컴파일 시 표준 에러 (stderr) 메시지

subsequence.cpp:7:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
subsequence.cpp:9:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++)scanf("%lld",&a[i]);
                      ~~~~~^~~~~~~~~~~~~~
subsequence.cpp:10:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++)scanf("%lld",&k[i]),dp[i]=1;
                      ~~~~~~~~~~~~~~~~~~~^~~~~~~~

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