Submission #6518870

---

Source Code Expand

#include <iostream>
#include <algorithm>

using std::cout;
using std::endl;
using std::cin;
using std::max;

int X[100'010];
int Y[100'010];
const bool WHITE = true;
const bool BLACK = !WHITE;
bool C[100'010];

int plane[2'010][2'010];

int main() {
	// Input
	int N;
	int K;
	cin >> N >> K;
	const int k2 = 2 * K;
	for(int i = 0; i < N; ++i) {
		char c;
		cin >> X[i] >> Y[i] >> c;
		X[i] %= k2;
		Y[i] %= k2;
		C[i] = c == 'W'? WHITE : BLACK;
	}
	// Preparation
	int blackCount = 0;
	for(int i = 0; i < N; ++i) {
		C[i] += (X[i] / K) + (Y[i] / K);
		X[i] %= K;
		Y[i] %= K;
		plane[X[i]][Y[i]] += (C[i] == WHITE);
		if(C[i] == BLACK) ++blackCount;
	}
	for(int x = 0; x < K; ++x)
		for(int y = 1; y < K; ++y)
			plane[x][y] += plane[x][y-1];
	for(int x = 1; x < K; ++x)
		for(int y = 0; y < K; ++y)
			plane[x][y] += plane[x-1][y];
	// Calculation
	int ans = 0;
	for(int x = 0; x < K; ++x)
		for(int y = 0; y < K; ++y) {
			int w = plane[K-1][K-1] - plane[x][K-1] - plane[K-1][y] + plane[x][y] * 2 + blackCount;
			ans = max(ans, max(w, N-w));
	}
	// Output
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result