제출 #333552

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

subsequence

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],b[100005],i,dp[1<<21],mx,c[100005],path[100005],x,mask[256],id[256];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=1;i<=n;i++){
        c[i]=1;
        if(n<5001){
            for(int j=1;j<i;j++){
                if(__builtin_popcount(a[j]&a[i])==b[i]&&c[i]<c[j]+1){
                    c[i]=c[j]+1;
                    path[i]=j;
                }
            }
        }else{
            for(int j=0;j<256;j++){
                if(__builtin_popcount(j&a[i])==b[i]&&c[i]<mask[j]+1){
                    c[i]=mask[j]+1;
                    path[i]=id[j];
                }
            }
            if(c[i]>mask[a[i]]){
                mask[a[i]]=c[i];
                id[a[i]]=i;
            }
        }
        if(c[i]>mx){
            mx=c[i];
            x=i;
        }
    }
    printf("%d\n",mx);
    stack<int>st;
    while(x){
        st.push(x);
        x=path[x];
    }
    while(!st.empty()){
        printf("%d ",st.top());
        st.pop();
    }
}

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

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

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