Submission #843941

#	Time	Username	Problem	Language	Result	Execution time	Memory
843941		biximo	Council (JOI23_council)	C++17	0 / 100	247 ms	179288 KiB

council

#include <bits/stdc++.h>
using namespace std;
using p = pair<int, int>;
int n, m, te, bits[20] = {0};
p dp[1048576][21];
bool poss[1048576] = {0};
vector<int> council, cnts, dpCouncils;
int main() {
    for(auto&i: dp) for(auto&j: i) j = {0, 0};
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    council.resize(n);
    for(auto&i: council) {
        i = 0;
        for(int j = 0; j < m; j ++) {
            cin >> te;
            if(te) {
                i += (1 << j);
                bits[j] ++;
            }
        }
        poss[((1 << m) - 1) & (~i)] = 1;
    }
    for(auto&i: council) {
        int ni = 0;
        int cnt = 0;
        for(int j = 0; j < m; j ++) {
            int cb = bits[j];
            if(i & (1 << j)) cb --;
            if(cb - 1 >= (n) / 2) {
                cnt ++;
            }
            else if(cb >= (n) / 2) {
                ni += (1 << j);
            }
        }
        dpCouncils.push_back(ni);
        cnts.push_back(cnt);
    }
    for(int i = 0; i < (1 << m); i ++) {
        dp[i][0] = {(poss[i] ? __builtin_popcount(i) : 0), 0};
        if((poss[i] ? __builtin_popcount(i) : 0) == 10) {
//            cout << i << "\n";
        }
    }
    for(int j = 1; j <= m; j ++) {
        for(int i = 0; i < (1 << m); i ++) {
            int max1 = dp[i][j - 1].first;
            int max2 = dp[i][j - 1].second;
            auto c = ((i & (1 << (j - 1))) ? dp[i - (1 << (j - 1))][j - 1] : pair<int, int>(dp[i + (1 << (j - 1))][j - 1].first - 1, dp[i + (1 << (j - 1))][j - 1].second - 1));
            if(max1 >= c.first) max2 = max(max2, c.first);
            else {
                max2 = max(max1, c.second);
                max1 = c.first;
            }
            dp[i][j] = {max1, max2};
        }
    }
    for(int i = 0; i < n; i ++) {
        int maxV = 0;
        for(int j = 0; j < m; j ++) {
            int cb = bits[j];
            if(council[i] & (1 << j)) cb --;
            if(cb - 1 >= (n) / 2) {
            }
            else if(cb >= (n) / 2) {
                if(!(council[i] & (1 << j))) maxV ++;
            }
        }
//        cout << maxV << "\n";
//        cout << cnts[i] << "\n";
        cout << cnts[i] + ((maxV == dp[dpCouncils[i]][m].first) ? dp[dpCouncils[i]][m].second : dp[dpCouncils[i]][m].first) << "\n";
        assert(cnts[i] + (maxV == dp[dpCouncils[i]][m].first ? dp[dpCouncils[i]][m].second : dp[dpCouncils[i]][m].first) <= m);
//        cout << cnts[i] << "\n";
    }
}

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