Submission #17429724


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int N,M,s[40][1000],a,b,c,n,m,cnt,detx[1000],dety[1000],dp1[1<<20],dp2[1<<20],ok[20],ch[1<<20],ans,MAX;
vector<P> vv;
int main(){
    cin>>n>>m;
    if(n==0)return 0;
    cnt=0;
    ans=1;
    for(int i=0;i<20;i++)ok[i]=0;
    for(int i=0;i<m;i++){
        cin>>detx[i]>>dety[i];
        detx[i]--;
        dety[i]--;
    }
    cnt=m;
    N=n/2;
    M=n-n/2;
    for(int i=0;i<(1<<N);i++){
        c=0;
        for(int j=0;j<N;j++){
            if((i>>j)&1)c++;
        }
        dp1[i]=c;
    }

    for(int i=0;i<(1<<M);i++){
        c=0;
        for(int j=0;j<M;j++){
            if((i>>j)&1)c++;
        }
        dp2[i]=c;
    }



    for(int i=0;i<cnt;i++){
        a=detx[i],b=dety[i];
        if(a<N&&b<N)dp1[(1<<a)|(1<<b)]=0;
        else if(a>=N&&b>=N){
            a-=N;
            b-=N;
           dp2[(1<<a)|(1<<b)]=0;
        }
        else{
            if(a>b)swap(a,b);
            //cout<<"a"<<" "<<a<<" "<<b<<endl;
            b-=N;
            ok[a]|=(1<<b);
        }

    }

    for(int i=1;i<(1<<N);i++){
        if(dp1[i]==0){
            for(int j=0;j<N;j++){
                dp1[i|(1<<j)]=0;
            }
        }
    }
    for(int i=1;i<(1<<M);i++){
        if(dp2[i]==0){
            for(int j=0;j<M;j++){
                dp2[i|(1<<j)]=0;
            }
        }
    }
    for(int i=1;i<(1<<M);i++){
        for(int j=0;j<M;j++){
            dp2[i|(1<<j)]=max(dp2[i|(1<<j)],dp2[i]);
        }
    }

    for(int i=0;i<N;i++){
        ok[i]=((1<<M)-1)^ok[i];
        //cout<<i<<" "<<ok[i]<<endl;
    }
    for(int i=0;i<(1<<N);i++){
        ch[i]=(1<<M)-1;
        for(int j=0;j<N;j++){
            if((i>>j)&1){
                ch[i]&=ok[j];
            }
        }
    }
    for(int i=0;i<(1<<N);i++){
        //cout<<i<<" "<<dp1[i]<<" "<<ch[i]<<" "<<dp2[ch[i]]<<" "<<ans<<endl;
        if(dp1[i]){
            MAX=dp1[i]+dp2[ch[i]];
            ans=max(ans,MAX);
        }
    }
    cout<<ans<<endl;
}

Submission Info

Submission Time
Task G - Mixture Drug
User alorie
Language C++ (GCC 9.2.1)
Score 600
Code Size 2121 Byte
Status
Exec Time 165 ms
Memory 15940 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
× 3
× 51
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_3.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_4.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt 8 ms 3652 KB
sample_02.txt 3 ms 3544 KB
sample_03.txt 3 ms 3472 KB
subtask_1_1.txt 2 ms 3616 KB
subtask_1_10.txt 162 ms 15868 KB
subtask_1_11.txt 3 ms 3552 KB
subtask_1_12.txt 159 ms 15712 KB
subtask_1_13.txt 102 ms 11788 KB
subtask_1_14.txt 146 ms 15756 KB
subtask_1_15.txt 2 ms 3664 KB
subtask_1_16.txt 158 ms 15900 KB
subtask_1_17.txt 160 ms 15940 KB
subtask_1_18.txt 162 ms 15756 KB
subtask_1_19.txt 3 ms 3672 KB
subtask_1_2.txt 138 ms 15868 KB
subtask_1_20.txt 159 ms 15828 KB
subtask_1_21.txt 162 ms 15708 KB
subtask_1_22.txt 160 ms 15696 KB
subtask_1_23.txt 2 ms 3424 KB
subtask_1_24.txt 16 ms 4188 KB
subtask_1_25.txt 160 ms 15932 KB
subtask_1_26.txt 161 ms 15872 KB
subtask_1_27.txt 165 ms 15892 KB
subtask_1_28.txt 163 ms 15824 KB
subtask_1_29.txt 160 ms 15740 KB
subtask_1_3.txt 37 ms 5648 KB
subtask_1_30.txt 3 ms 3548 KB
subtask_1_31.txt 2 ms 3604 KB
subtask_1_32.txt 3 ms 3512 KB
subtask_1_33.txt 15 ms 4128 KB
subtask_1_34.txt 153 ms 15904 KB
subtask_1_35.txt 163 ms 15736 KB
subtask_1_36.txt 164 ms 15828 KB
subtask_1_37.txt 162 ms 15904 KB
subtask_1_38.txt 163 ms 15852 KB
subtask_1_39.txt 160 ms 15756 KB
subtask_1_4.txt 164 ms 15700 KB
subtask_1_40.txt 162 ms 15900 KB
subtask_1_41.txt 162 ms 15876 KB
subtask_1_42.txt 163 ms 15892 KB
subtask_1_43.txt 157 ms 15844 KB
subtask_1_44.txt 158 ms 15888 KB
subtask_1_45.txt 154 ms 15908 KB
subtask_1_46.txt 144 ms 15872 KB
subtask_1_47.txt 161 ms 15700 KB
subtask_1_48.txt 155 ms 15696 KB
subtask_1_5.txt 48 ms 6696 KB
subtask_1_6.txt 161 ms 15900 KB
subtask_1_7.txt 62 ms 7652 KB
subtask_1_8.txt 160 ms 15928 KB
subtask_1_9.txt 86 ms 9800 KB