Submission #1005847

#TimeUsernameProblemLanguageResultExecution timeMemory
1005847pccCouncil (JOI23_council)C++17
78 / 100
4073 ms13152 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,popcnt,sse4") #define ll long long #define pll pair<ll,ll> #define pii pair<int,int> #define fs first #define sc second #define tlll tuple<ll,ll,ll> const int mxn = 3e5+10; const int B = 20; int ans[1<<B],arr[mxn]; int dp[1<<B]; bitset<(1<<B)> done; //int dp[1<<(10)][1<<(10)];//left = l,min of popcnt(right & r) int mask[mxn]; int cnt[B]; int N,M; int sh[mxn]; int rmask; int tl,tr; int pull(int tar){ int re = B+1; for(int i = 0;i<(1<<tl);i++){ //int tmp = __builtin_popcount((i<<tr)&tar)+dp[i][tar&rmask]; int tmp = __builtin_popcount((i<<tr)&tar)+dp[(i<<tr)|(tar&rmask)]; re = min(re,tmp); } return re; } void push(int now){ if(done[now])return; for(int i = 0;i<(1<<tr);i++){ int tmp = __builtin_popcount(i&now); dp[((now>>tr)<<tr)|i] = min(dp[((now>>tr)<<tr)|i],tmp); //dp[now>>tr][i] = min(dp[now>>tr][i],tmp); } return; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>N>>M; tl = M>>1,tr = M-tl; rmask = (1<<tr)-1; memset(ans,-1,sizeof(ans)); for(int i = 0;i<N;i++){ for(int j = 0;j<M;j++){ int k; cin>>k; if(k)arr[i] |= 1<<j,cnt[j]++; } ans[i] = B+1; } for(int i = 0;i<N;i++){ for(int j = 0;j<M;j++){ if(arr[i]&(1<<j))cnt[j]--; if(cnt[j]>=N/2)sh[i]++; if(cnt[j] == N/2)mask[i]|=1<<j; if(arr[i]&(1<<j))cnt[j]++; } } fill(dp,dp+(1<<B),B+1); //for(auto &i:dp)for(auto &j:i)j = B+1; for(int i = 0;i<N;i++){ ans[i] = pull(mask[i]); push(arr[i]); } fill(dp,dp+(1<<B),B+1); done.reset(); //for(auto &i:dp)for(auto &j:i)j = B+1; for(int i = N-1;i>=0;i--){ ans[i] = min(ans[i],pull(mask[i])); push(arr[i]); } for(int i = 0;i<N;i++){ cout<<sh[i]-ans[i]<<'\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...