Submission #961877

#	Time	Username	Problem	Language	Result	Execution time	Memory
961877		RaresFelix	Council (JOI23_council)	C++17	100 / 100	1975 ms	127060 KiB

council

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ld = long double;  // or double, if TL is tight
using str = string; 
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;


int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<vi> A(n, vi(m, 0));
    vi B(n, 0);
    vector<vector<ii> > DP(1 << m); /// DP[bm] -> min popcnt(x & bm) pt x in A 
    vi Fr(m, 0);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            cin >> A[i][j];
            Fr[j] += A[i][j];
            if(A[i][j]) B[i] |= 1 << j;
        }
        DP[(~B[i]) & ((1 << m) - 1)].push_back({0, i});
    }
    auto clean = [&](int bm) {
        if(DP[bm].size() <= 2) return;
        sort(all(DP[bm]));
        if(DP[bm][0].second == DP[bm][1].second)
            DP[bm][1] = DP[bm][2];
        DP[bm].resize(2);
    };
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < (1 << m); ++j) {
            sort(all(DP[j]));
            clean(j);
            for(auto [cost, orig] : DP[j]) {
                int jj = j ^ (1 << i), cnou = cost;
                if(!(j & (1 << i))) cnou++;
                DP[jj].push_back({cnou, orig});
                clean(jj);
            }
        }
    for(int i = 0; i < n; ++i) {
        int bm = 0, cre = 0;
        for(int j = 0; j < m; ++j) {
            if(Fr[j] - A[i][j] >= n / 2 + 1) {
                ++cre; continue;
            }
            if(Fr[j] - A[i][j] < n / 2) continue;
            if(Fr[j] - A[i][j] == n / 2) {
                bm |= (1 << j);
            }
        }
        int tmp = __builtin_popcount(bm);
        for(auto [cost, orig] : DP[bm])
            if(orig != i) tmp = min(tmp, cost);
        cre += __builtin_popcount(bm) - tmp;
        cout << cre << "\n";
    }
    return 0;
}

• 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