제출 #989157

#제출 시각아이디문제언어결과실행 시간메모리
989157AlphaMale06Council (JOI23_council)C++17
16 / 100
4083 ms17368 KiB
#include <bits/stdc++.h> using namespace std; const int N = 300001; const int M = 20; const int to = 1024; int a[N], sum[M], ans[N], mn[N], masks[N]; int dp[to][to], ppcnt[to][to]; short l[1<<M], r[1<<M]; void smin(int & x, int y){ if(x>y)x=y; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; for(int i=0; i< n; i++){ for(int j=0; j< m; j++){ int x; cin >> x; a[i]+=x<<j; sum[j]+=x; } } for(int i=0; i< n; i++)mn[i]=1e9; for(int i=0; i< n; i++){ for(int j=0; j< m; j++)sum[j]-=(a[i] & (1<<j))>>j; for(int j=0; j< m; j++){ if(sum[j]>=n/2)ans[i]++; if(sum[j]==n/2)masks[i]+=1<<j; } for(int j=0; j< m; j++)sum[j]+=(a[i] & (1<<j))>>j; } for(int i=0; i< (1<<M); ++i){ l[i]=i>>10; r[i]=i & ((1<<10)-1); short f = l[i], s = r[i]; dp[f][s]=1e9; ppcnt[f][s]=__builtin_popcount(f & s); } for(int i=0; i< n-1; ++i){ short f = l[a[i]]; short s = r[a[i]]; for(short j = 0; j<to; ++j){ smin(dp[j][s], ppcnt[j][f]); } f = l[masks[i+1]]; s = r[masks[i+1]]; for(short j=0; j<to; ++j){ smin(mn[i+1], dp[f][j]+ppcnt[s][j]); } } for(int i=0; i< (1<<M); ++i)dp[l[i]][r[i]]=1e9; for(int i=n-1; i>0; i--){ short f = l[a[i]]; short s = r[a[i]]; for(short j = 0; j<to; ++j){ smin(dp[j][s], ppcnt[j][f]); } f = l[masks[i-1]]; s = r[masks[i-1]]; for(short j=0; j<to; ++j){ smin(mn[i-1], dp[f][j]+ppcnt[s][j]); } } for(int i=0; i< n; i++){ cout << ans[i]-mn[i] << '\n'; } }
#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...