Submission #1207539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207539		siewjh	Council (JOI23_council)	C++20	0 / 100	58 ms	16712 KiB

council

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1100000;
pair<int, int> dp[MAXN][2];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int ppl, bills; cin >> ppl >> bills;
	vector<int> bcnt(bills), mv(ppl);
	for (int i = 0; i < ppl; i++){
		int imsk = 0;
		for (int j = 0; j < bills; j++){
			int x; cin >> x;
			if (x){
				bcnt[j]++; imsk += (1 << j);
			}
		}
		mv[i] = imsk;
	}
	int alw = 0, bm0 = 0, bm1 = 0;
	for (int i = 0; i < bills; i++){
		if (bcnt[i] >= (ppl >> 1) + 2) alw++;
		else if (bcnt[i] == (ppl >> 1) + 1) bm1 += (1 << i);
		else if (bcnt[i] == (ppl >> 1)) bm0 += (1 << i);
	}
	for (int i = (1 << bills) - 1; i >= 0; i--) dp[i][0] = dp[i][1] = {0, -1};
	for (int i = 0; i < ppl; i++){
		int rev = ((1 << bills) - 1) ^ mv[i];
		dp[rev][0] = {__builtin_popcount(rev), i};
	}
	for (int i = 0; i < bills; i++)
		for (int mask = (1 << bills) - 1; mask >= 0; mask--)
			if ((mask & (1 << i)) == 0){
				int trm = mask ^ (1 << i);
				if (dp[trm][0].first - 1 > dp[mask][0].first){
					if (dp[trm][0].second != dp[mask][0].second) dp[mask][1] = dp[mask][0];
					dp[mask][0] = {dp[trm][0].first - 1, dp[trm][0].second};
					if (dp[trm][1].first - 1 > dp[mask][1].first) dp[mask][1] = {dp[trm][1].first - 1, dp[trm][1].second};
				}
				else if (dp[trm][0].first - 1 > dp[mask][1].first){
					if (dp[trm][0].second != dp[mask][0].second) dp[mask][1] = {dp[trm][0].first - 1, dp[trm][0].second};
					else if (dp[trm][1].first - 1 > dp[mask][1].first) dp[mask][1] = {dp[trm][1].first - 1, dp[trm][1].second};
				}
			}
	for (int i = 0; i < bills; i++)
		for (int mask = (1 << bills) - 1; mask >= 0; mask--)
			if (mask & (1 << i)){
				int trm = mask ^ (1 << i);
				if (dp[trm][0].first > dp[mask][0].first){
					if (dp[trm][0].second != dp[mask][0].second) dp[mask][1] = dp[mask][0];
					dp[mask][0] = dp[trm][0];
					if (dp[trm][1].first > dp[mask][1].first) dp[mask][1] = dp[trm][1];
				}
				else if (dp[trm][0].first > dp[mask][1].first){
					if (dp[trm][0].second != dp[mask][0].second) dp[mask][1] = dp[trm][0];
					else if (dp[trm][1].first > dp[mask][1].first) dp[mask][1] = dp[trm][1];
				}
			}
	for (int i = 0; i < ppl; i++){
		int ans = alw + __builtin_popcount(bm1 & ~mv[i]);
		int mask = (bm1 & mv[i]) | (bm0 & ~mv[i]);
		int ext = (dp[mask][0].second == i ? dp[mask][1].first : dp[mask][0].first);
		cout << ans + ext << '\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