Problem:
 Score : 500 points    Problem Statement AtCoDeer is thinking of painting an infinite two-dimensional grid in a checked pattern of side K .
Here, a checked pattern of side K is a pattern where each square is painted black or white so that each connected component of each color is a K  ×  K square.
Below is an example of a checked pattern of side 3 :     AtCoDeer has N desires.
The i -th desire is represented by x_i , y_i and c_i .
If c_i is B , it means that he wants to paint the square (x_i,y_i) black; if c_i is W , he wants to paint the square (x_i,y_i) white.
At most how many desires can he satisfy at the same time?      Constraints  1  ≤  N  ≤  10^5  1  ≤  K  ≤  1000  0  ≤  x_i  ≤  10^9  0  ≤  y_i  ≤  10^9  If i  ≠  j , then (x_i,y_i)  ≠  (x_j,y_j) .  c_i is B or W .  N , K , x_i and y_i are integers.         Input Input is given from Standard Input in the following format:  N  K  x_1  y_1  c_1  x_2  y_2  c_2  :  x_N  y_N  c_N       Output Print the maximum number of desires that can be satisfied at the same time.        Sample Input 1 4 3
0 1 W
1 2 W
5 3 B
5 4 B      Sample Output 1 4  He can satisfy all his desires by painting as shown in the example above.       Sample Input 2 2 1000
0 0 B
0 1 W      Sample Output 2 2       Sample Input 3 6 2
1 2 B
2 1 W
2 2 B
1 0 B
0 6 W
4 5 W      Sample Output 3 4

Solution (Python):
from itertools import accumulate

n, k = map(int, input().split())
k2 = k * 2
req_b = [[0] * k for _ in range(k)]
req_w = [[0] * k for _ in range(k)]
bc, wc = 0, 0
for i in range(n):
    x, y, c = input().split()
    x, y = int(x), int(y)
    rx, ry = x % k2, y % k2
    b = c == 'B'
    if rx >= k:
        rx -= k
        if ry >= k:
            ry -= k
        else:
            b = not b
    elif ry >= k:
        ry -= k
        b = not b
    if b:
        req_b[rx][ry] += 1
        bc += 1
    else:
        req_w[rx][ry] += 1
        wc += 1

req_b = [list(accumulate(req)) for req in req_b]
req_w = [list(accumulate(req)) for req in req_w]
req_b = [list(accumulate(req)) for req in zip(*req_b)]
req_w = [list(accumulate(req)) for req in zip(*req_w)]

ans = 0
kb, kw = req_b[-1], req_w[-1]
for dx_b, dx_w in zip(req_b, req_w):
    dxk_b = dx_b[-1]
    dxk_w = dx_w[-1]
    for b1, w1, kyb, kyw in zip(dx_b, dx_w, kb, kw):
        b = bc - kyb - dxk_b + b1 * 2
        w = wc - kyw - dxk_w + w1 * 2
        a = b + wc - w
        ans = max(ans, a, n - a)
print(ans)

Solution (Python):
from itertools import accumulate

n, k = map(int, input().split())
k2 = k * 2
req_b = [[0] * k for _ in range(k)]
req_w = [[0] * k for _ in range(k)]
bc, wc = 0, 0
for i in range(n):
    x, y, c = input().split()
    x, y = int(x), int(y)
    rx, ry = x % k2, y % k2
    b = c == 'B'
    if rx >= k:
        rx -= k
        if ry >= k:
            ry -= k
        else:
            b = not b
    elif ry >= k:
        ry -= k
        b = not b
    if b:
        req_b[rx][ry] += 1
        bc += 1
    else:
        req_w[rx][ry] += 1
        wc += 1

req_b = [list(accumulate(req)) for req in req_b]
req_w = [list(accumulate(req)) for req in req_w]
req_b = [list(accumulate(req)) for req in zip(*req_b)]
req_w = [list(accumulate(req)) for req in zip(*req_w)]

ans = 0
kb, kw = req_b[-1], req_w[-1]
for dx, (dx_b, dx_w) in enumerate(zip(req_b, req_w)):
    dxk_b = dx_b[-1]
    dxk_w = dx_w[-1]
    for b1, w1, kyb, kyw in zip(dx_b, dx_w, kb, kw):
        b = bc - kyb - dxk_b + b1 * 2
        w = wc - kyw - dxk_w + w1 * 2
        a = b + wc - w
        ans = max(ans, a, n - a)
print(ans)

Solution (Python):

from itertools import accumulate
def inpl(): return tuple(map(int, input().split()))
N, K = inpl()
P = [[0 for _ in range(2*K)] for _ in range(K)]

for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c=="W":
        y += K
    x, y = x%(2*K), y%(2*K)
    if x >= K:
        if y < K:
            x -= K
            y += K
        else:
            x -= K
            y -= K
    
    P[0][y] += 1
    if x == K-1:
        if y == K-1:
            pass
        elif y > K-1:
            P[0][y-K] -= 1
        elif y < K-1:
            P[0][-1] += 1
            P[0][y+K] -= 1
    else:
        if y == K-1:
            P[x+1][-1] += 1
            P[x+1][y] -= 2
        elif y == 2*K-1:
            P[x+1][y-K] += 2
            P[x+1][y] -= 1
            P[0][y-K] -= 1
        elif y > K-1:
            P[x+1][-1] += 1
            P[x+1][y-K] += 2
            P[x+1][y] -= 2
            P[0][y-K] -= 1
        elif y < K-1:
            P[0][-1] += 1
            P[x+1][y+K] += 2
            P[x+1][-1] -= 1
            P[0][y+K] -= 1
            P[x+1][y] -= 2

S1 = [list(accumulate(l)) for l in zip(*P)]
S2 = [max(list(accumulate(l[::-1]))) for l in zip(*S1)]

print(max(S2))

Solution (Python):
from itertools import accumulate

n, k = map(int, input().split())
k2 = k * 2
req_b = [[0] * k for _ in range(k)]
req_w = [[0] * k for _ in range(k)]
bc, wc = 0, 0
for i in range(n):
    x, y, c = input().split()
    x, y = int(x), int(y)
    rx, ry = x % k2, y % k2
    b = c == 'B'
    if rx >= k:
        rx -= k
        if ry >= k:
            ry -= k
        else:
            b = not b
    elif ry >= k:
        ry -= k
        b = not b
    if b:
        req_b[rx][ry] += 1
        bc += 1
    else:
        req_w[rx][ry] += 1
        wc += 1

req_b[0] = list(accumulate(req_b[0]))
req_w[0] = list(accumulate(req_w[0]))

for i in range(1, k):
    req_b[i][0] += req_b[i - 1][0]
    req_w[i][0] += req_w[i - 1][0]
    for j in range(1, k):
        req_b[i][j] += req_b[i][j - 1] + req_b[i - 1][j] - req_b[i - 1][j - 1]
        req_w[i][j] += req_w[i][j - 1] + req_w[i - 1][j] - req_w[i - 1][j - 1]

ans = 0
for dx in range(k):
    dxk_b = req_b[dx][-1]
    dxk_w = req_w[dx][-1]
    for dy in range(k):
        b1 = req_b[dx][dy]
        b2 = bc - req_b[k - 1][dy] - dxk_b + b1
        w1 = req_w[dx][dy]
        w2 = wc - req_w[k - 1][dy] - dxk_w + w1
        b, w = b1 + b2, w1 + w2
        ans = max(ans, b + wc - w, w + bc - b)
        
print(ans)

Solution (Python):
N,K = map(int,input().split())

import numpy as np
blacks = np.zeros((2*K,2*K), dtype=int)

offset = 0

for _ in range(N):
  x,y,c = input().split()
  x,y = int(x),int(y)
  x %= 2*K
  y %= 2*K
  if c == 'B':
    blacks[x,y] += 1
  else:
    blacks[x,y] -= 1
    offset += 1

m = np.zeros((3*K,2*K),dtype=int)
m[:2*K,:] = blacks
m[2*K:,:] = blacks[:K,:]

np.cumsum(m,axis=0, out=m)

m = m[K:,:] - m[:2*K,:]

n = np.zeros((2*K,3*K),dtype=int)
n[:,:2*K] = m
n[:,2*K:] = m[:,:K]

np.cumsum(n,axis=1, out=n)
n = n[:,K:] - n[:,:2*K]

m = np.zeros((3*K,3*K),dtype=int)
m[:2*K,:2*K] = n
m[2*K:,:2*K] = n[:K,:]
m[:2*K,2*K:] = n[:,:K]
m[2*K:,2*K:] = n[:K,:K]

m = m[:2*K,:2*K] + m[K:,K:]
m = m.max()

print(m+offset)