Submission #1280579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280579		Icelast	Council (JOI23_council)	C++20	100 / 100	531 ms	71680 KiB

council

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n+1, vector<int>(m));
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    vector<int> b(n+1, 0), cb(n+1, 0);
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j]){
                b[i] += (1<<j);
            }else{
                cb[i] += (1<<j);
            }
        }
    }
    auto chmax = [&](auto &a, auto b) -> void{
        auto fetch = b[0];
        if(a[0] < fetch) swap(a[0], fetch);
        if(a[1] < fetch && a[0].second != fetch.second) swap(a[1], fetch);
        fetch = b[1];
        if(a[1] < fetch && a[0].second != fetch.second) swap(a[1], fetch);
    };
    array<pair<int, int>, 2> I = {make_pair(0, -1), make_pair(0, -1)};
    int full = (1<<m)-1;
    vector<array<pair<int, int>, 2>> dp1(full+1, I);
    vector<array<pair<int, int>, 2>> dp2(full+1, I);
    for(int i = 1; i <= n; i++){
        array<pair<int, int>, 2> t = {make_pair(i, i), make_pair(0, -1)};
        chmax(dp1[cb[i]], t);
    }
    for(int i = 0; i < m; i++){
        for(int mask = full; mask >= 0; mask--){
            if(!(mask & (1<<i))){
                chmax(dp1[mask], dp1[mask^(1<<i)]);
            }
        }
    }
    for(int mask = 0; mask <= full; mask++){
        int pc = __builtin_popcount(mask);
        if(dp1[mask][0].second != -1){
            dp1[mask][0].first = pc;
        }
        if(dp1[mask][1].second != -1){
            dp1[mask][1].first = pc;
        }
    }
    for(int mask = 0; mask <= full; mask++){
        chmax(dp2[mask], dp1[mask]);
    }
    for(int i = 0; i < m; i++){
        for(int mask = 0; mask <= full; mask++){
            if(mask & (1<<i)){
                chmax(dp2[mask], dp2[mask^(1<<i)]);
            }
        }
    }
    vector<int> d(m, 0);
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < m; j++){
            d[j] += a[i][j];
        }
    }
    vector<int> e(m);
    int K = n/2;
    for(int i = 1; i <= n; i++){
        int S = 0, ans = 0;
        for(int j = 0; j < m; j++){
            e[j] = d[j] - a[i][j];
            if(e[j] > K){
                ans++;
            }
            if(e[j] == K){
                S |= (1<<j);
            }
        }
        if(dp2[S][0].second != i){
            ans += dp2[S][0].first;
        }else{
            ans += dp2[S][1].first;
        }
        cout << ans << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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