Submission #891340

#TimeUsernameProblemLanguageResultExecution timeMemory
891340iskhakkutbilimCouncil (JOI23_council)C++17
100 / 100
2707 ms58408 KiB
#include <bits/stdc++.h> using namespace std; #define ff first #define ss second #define all(a) a.begin(), a.end() const int N = 3e5; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; int a[n][m]; pair<int, int> dp[2][1024][1024]; for(int i = 0;i < n; i++){ for(int j = 0;j < m; j++){ cin >> a[i][j]; } } vector<int> cnt(m,0); vector<int> bits(n, 0); int bpc[1<<20]; for(int i = 0;i < 1<<20; i++){ bpc[i] = __builtin_popcount(i); } for(int i = 0;i < 2; i++){ for(int j = 0;j < 1024; j++){ for(int k = 0;k < 1024; k++){ dp[i][j][k] = {-1, -1}; } } } for(int i = 0;i < n; i++){ for(int j = 0;j < m; j++){ bits[i]+= (a[i][j] << j); cnt[j]+= a[i][j]; } int m0 = bits[i] & 1023; int m1 = bits[i]>>10; for(int j = 0;j < 1024; j++){ int c = bpc[m1 & j]; if(dp[0][m0][j].ff == -1){ dp[0][m0][j] = {c, i}; }else{ if(dp[0][m0][j].ff >= c){ dp[1][m0][j] = dp[0][m0][j]; dp[0][m0][j] = {c, i}; }else if(dp[1][m0][j].ff == -1 || dp[1][m0][j].ff >= c){ dp[1][m0][j] = {c, i}; } } } } for(int i = 0;i < n; i++){ int mask = 0, bc = 0; for(int j = 0;j < m; j++){ if(bits[i] & (1<<j)){ if(cnt[j] == n/2 + 1){ bc++; mask+= (1<<j); }else if(cnt[j] > n/2+1){ bc++; } }else{ if(cnt[j] > n / 2) bc++; else if(cnt[j] == n / 2){ mask+= (1<<j); bc++; } } } int mn = m; int m0 = mask & 1023; int m1 = mask >> 10; for(int j = 0;j < 1024; j++){ int c = bpc[m0 & j]; if(dp[0][j][m1].ff == -1) continue; int kek = 20; if(dp[0][j][m1].ss != i && dp[0][j][m1].ss != -1){ kek = min(kek, dp[0][j][m1].ff); } else if(dp[1][j][m1].ss != i && dp[1][j][m1].ss != -1){ kek = min(kek, dp[1][j][m1].ff); } mn = min(mn, kek + c); } cout << bc-mn << '\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...