Submission #921264

#TimeUsernameProblemLanguageResultExecution timeMemory
921264denniskimCouncil (JOI23_council)C++17
100 / 100
3491 ms132992 KiB
#include <bits/stdc++.h> using namespace std; typedef int ll; typedef __int128 lll; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<ld, ld> pld; #define MAX 9223372036854775807LL #define MIN -9223372036854775807LL #define INF 0x3f3f3f3f3f3f3f3f #define fi first #define se second #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10); #define sp << " " #define en << "\n" #define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end()) ll n, m; ll A[300010][21]; ll a[300010]; ll siz; ll dp1[2000010]; ll dp2[2000010][21]; ll cou[21]; ll b[21]; ll pas[21][21]; ll two, one, zero; int main(void) { fastio cin >> n >> m; siz = (1LL << m) - 1; for(ll i = 1 ; i <= n ; ++i) { for(ll j = 0 ; j < m ; ++j) { cin >> A[i][j]; a[i] += (1LL << j) * A[i][j]; cou[j] += A[i][j]; } a[i] ^= siz; dp1[a[i]]++; } for(ll i = 0 ; i < m ; ++i) { for(ll j = siz ; j >= 0 ; j--) { if(j & (1LL << i)) dp1[j ^ (1LL << i)] += dp1[j]; } } for(ll i = 0 ; i <= siz ; ++i) dp2[i][__builtin_popcount(i)] += dp1[i]; for(ll i = 0 ; i <= m ; ++i) { for(ll j = 0 ; j < m ; ++j) { for(ll k = 0 ; k <= siz ; k++) { if(k & (1LL << j)) dp2[k][i] += dp2[k ^ (1LL << j)][i]; } } } pas[0][0] = 1; for(ll i = 1 ; i <= 20 ; ++i) { pas[i][0] = pas[i][i] = 1; for(ll j = 1 ; j < i ; ++j) pas[i][j] = pas[i - 1][j - 1] + pas[i - 1][j]; } for(ll i = 0 ; i < m ; ++i) { if(cou[i] >= n / 2 + 2) two |= (1LL << i); else if(cou[i] == n / 2 + 1) one |= (1LL << i); else if(cou[i] == n / 2) zero |= (1LL << i); } for(ll i = 1 ; i <= n ; ++i) { ll ONE = two | (one & a[i]); ll ZERO = (one & (~a[i])) | (zero & a[i]); for(ll j = 0 ; j <= m ; ++j) b[j] = dp2[ZERO][j]; ll gap = (a[i] & ZERO); ll COU = __builtin_popcount(gap); for(ll j = 0 ; j <= COU ; ++j) b[j] -= pas[COU][j]; ll ans = 0; for(ll j = 0 ; j <= m ; ++j) { if(b[j]) ans = max(ans, j); } cout << ans + __builtin_popcount(ONE) en; } 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...