제출 #1154139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1154139		Younis_Dwai	Council (JOI23_council)	C++20	25 / 100	152 ms	8500 KiB

council

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define pf push_front
#define popf pop_frot
#define popb pop_back
//#define int long long
#define in insert
//#define mid (l+r)/2
using namespace std;
const int N=3e5+5;
bool b[N][21];
int best[N],n,m,V[N],cnt[21],ans[N],vis[N],ret=0,need;
void R(int k , int p){
     if(cnt[k]==need && b[p][k]==1) --ret;
     cnt[k]-=b[p][k];
     return ;
}
void A(int k , int p){
     if(cnt[k]==need-1 && b[p][k]==1) ++ret;
     cnt[k]+=b[p][k];
     return ;
}
void R1(int k , int m1,int m2){
     int was=cnt[k];
     cnt[k]-=bool(m1&(1<<(k-1)))+bool(m2&(1<<(k-1)));
     if(was>=need && cnt[k]<need) --ret;
     return ;
}
void A1(int k , int m1,int m2){
     int was=cnt[k];
     cnt[k]+=bool(m1&(1<<(k-1)))+bool((m2&(1<<(k-1))));
     if(was<need && cnt[k]>=need) ++ret;
     return ;
}
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>b[i][j];
            cnt[j]+=b[i][j];
            V[i]+=b[i][j]*((1<<(j-1)));
        }
        vis[V[i]]++;
    }
    need=(n)/2;
    for(int j=1;j<=m;j++){
            if(cnt[j]>=need) ++ret;
    }
    if(m<=10){
       for(int mask1=0;mask1<(1<<m);mask1++){
           for(int mask2=0;mask2<(1<<m);mask2++){
               vis[mask1]--;
               vis[mask2]--;
               if(vis[mask1]<0 || vis[mask2]<0){
                        vis[mask1]++;
                        vis[mask2]++;
                        continue ;
               }
               for(int k=1;k<=m;k++){
                   R1(k,mask1,mask2);
               }

               ans[mask1]=max(ans[mask1],ret);
               ans[mask2]=max(ans[mask2],ret);
               for(int k=1;k<=m;k++){
                   A1(k,mask1,mask2);
               }
               vis[mask1]++;
               vis[mask2]++;
           }
       }
    }
    else{
        for(int i=1;i<=n;i++){
            for(int j=1;j<i;j++){
                for(int k=1;k<=m;k++){
                    R(k,i);
                    R(k,j);
                }
                ans[i]=max(ans[i],ret);
                ans[j]=max(ans[j],ret);
                //cout<<" # "<<i<<' '<<j<<' '<<ret<<endl;
                for(int k=1;k<=m;k++){
                    A(k,i);
                    A(k,j);
                }
            }
        }
    }
    for(int i=1;i<=n;i++) cout<<ans[V[i]]<<endl;
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 19 / 19
• Subtask 5: 0 / 15
• Subtask 6: 0 / 22
• Subtask 7: 0 / 22