Submission #1206750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206750		PenguinsAreCute	Council (JOI23_council)	C++20	100 / 100	781 ms	92944 KiB

council

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, m;
	cin >> n >> m;
	int bt[n], zero = 0, one = 0, two = 0, cnt[m];
	memset(bt,0,sizeof(bt));
	memset(cnt,0,sizeof(cnt));
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++) {
			int a;
			cin >> a;
			cnt[j] += a;
			bt[i] |= (a << j);
		}
	for(int i=0;i<n;i++)
		bt[i] = ((1<<m)-1) & (~bt[i]);
	for(int i=0;i<m;i++)
		if(cnt[i] >= (n / 2) + 2)
			zero++;
		else if(cnt[i] == (n / 2) + 1)
			one |= (1 << i);
		else if(cnt[i] == (n / 2))
			two |= (1 << i);
	vector<vector<int>> dp(m+1,vector<int>(1<<m,-1e6));
	for(int i=0;i<n;i++)
		dp[m][bt[i]] = 0;
	auto up = [&dp,m](int i, int j) {
		int st = j & ((1 << m) - (1 << (m - i))), qry = j & ((1 << (m - i)) - 1);
		int qpt = qry & ~(1 << (m - i - 1));
		dp[i][j] = max(dp[i+1][st|qpt],dp[i+1][st|1<<(m-i-1)|qpt]+!!(qry&(1<<(m-i-1))));
	};
	for(int i=m;i--;)
		for(int j=0;j<(1<<m);j++)
			up(i, j);
	int btcnt[1<<m];
	memset(btcnt,0,sizeof(btcnt));
	for(int i=0;i<n;i++)
		btcnt[bt[i]]++;
	for(int i=0;i<n;i++) {
		int qmask = (one&~bt[i])|(two&bt[i]);
		if(btcnt[bt[i]] >= 2)
			cout << zero + __builtin_popcount(one & bt[i]) + dp[0][qmask] << "\n";
		else {
			dp[m][bt[i]] = -1e6;
			for(int j=m;j--;)
				up(j,(bt[i]&((1<<m)-(1<<(m-j))))|(qmask&((1<<(m-j))-1)));
			cout << zero + __builtin_popcount(one & bt[i]) + dp[0][qmask] << "\n";
			dp[m][bt[i]] = 0;
			for(int j=m;j--;)
				up(j,(bt[i]&((1<<m)-(1<<(m-j))))|(qmask&((1<<(m-j))-1)));
		}
	}
}

• 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