Submission #2531435

---

Source Code Expand

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n,k;
	cin >> n >> k;

	int x[n],y[n];
	rep(i,n){
		string c;
		cin >> x[i] >> y[i] >> c;

		// 黒で塗る基準に変換
		if(c == "W") x[i] += k;

		// 「市松模様の基準セル」（白正方形の左下セル）で市松模様を分類する
		// セルを塗ることができる塗り方の「市松模様の基準セル」はK*Kの正方形となるが、
		// その正方形の左下のセルに情報を変換
		x[i] += 2*k - (k-1);
		y[i] += 2*k - (k-1);
		x[i] %= 2*k;
		y[i] %= 2*k;
	}

	int a[2*k][2*k];
	rep(i,2*k) rep(j,2*k) a[i][j] = 0;

	rep(i,n){
		int r = y[i], c = x[i];
		a[r][c]++;

		a[(r+k) % (2*k)][c]--;
		if(r+k>=2*k) a[0][c]++;

		a[r][(c+k) % (2*k)]--;
		if(c+k>=2*k) a[r][0]++;

		a[(r+k) % (2*k)][(c+k) % (2*k)]++;
		if(r+k>=2*k || c+k>=2*k) a[0][0]++;
		if(r+k>=2*k) a[r-k][0]--;
		if(c+k>=2*k) a[0][c-k]--;
	}

	int s[2*k][2*k];
	rep(i,2*k) rep(j,2*k) s[i][j] = (i==0 || j==0) ? a[i][j] : 0;

	rep(i,2*k) rep(j,2*k-1) s[i][j+1] += s[i][j];
	rep(j,2*k) rep(i,2*k-1) s[i+1][j] += s[i][j];

	int ans = 0;
	rep(i,2*k) rep(j,2*k) ans = max(ans,s[i][j]);

	cout << ans << endl; 
}

Submission Info

Judge Result