Submission #4037320

---

Source Code Expand

from itertools import accumulate
from operator import add
 
N, K = map(int, input().split())
K2 = 2 * K
 
# Gss[i][j]: 「市松模様の黒い部分の右上のマス」が(i,j)のとき、満たせる要望の個数
Gss = [[0] * K2 for i in range(K2)]
 
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
 
    # 要望を「0<=x<2K, 0<=y<K, 'B'」に変換する
    if c == 'W':
        x -= K
    x, y = x % K2, y % K2
 
    if y >= K:
        x, y = (x - K) % K2, y - K
 
    # 要望を満たす「市松模様の黒い部分の右上のマス」に対して、+1する
    # （後で累積和を取る）
    Gss[x][y] += 1
    Gss[x][y - K] += -1
    if x != K:
        Gss[x - K][y - K] += 1
        Gss[x - K][y] += -1
    if x > K:
        Gss[0][y] += 1
        Gss[0][y - K] += -1
 
# 累積和を取る
Gss = [accumulate(Gs) for Gs in Gss]
Gss = [accumulate(Gs) for Gs in zip(*Gss)]
Gss = list(map(list, zip(*Gss))) # 転置
 
# 「K<=y<2K」の部分を、「0<=y<K」に重ね合わせる
Gss = [map(add, Gss[i][:K], Gss[i - K][K:]) for i in range(K2)]
 
# Gssの最大値が答え
print(max(map(max, Gss)))

Submission Info

Judge Result