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):
import sys
input=sys.stdin.readline
N,K=map(int,input().split())
L=[[0 for i in range(K*2+1)]for j in range(K*2+1)]
for i in range(N):
    x,y,c=list(input().split())
    if c=="W":
        x=int(x)+K
        y=int(y)
    else:
        x=int(x)
        y=int(y)
    L[x%(2*K)+1][y%(2*K)+1]+=1


for h in range(1,2*K+1):
    for w in range(1,2*K+1):
        L[h][w]=L[h-1][w]+L[h][w]

for h in range(1,2*K+1):
    for w in range(1,2*K+1):
        L[h][w]=L[h][w-1]+L[h][w]


ans=0
for h in range(1,K+1):
    for w in range(1,K+1):
        cnt=0
        for a in range(3):
            for b in range(3):
                if (a+b)%2==0:
                    HH=h+a*K
                    if h+a*K>2*K:
                        HH=2*K
                    HL=h+a*K-K
                    if h+a*K-K<0:
                        HL=0
                    WH=w+b*K
                    if w+b*K>2*K:
                        WH=2*K
                    WL=w+b*K-K
                    if w+b*K-K<0:
                        WL=0
                    cnt+=L[HH][WH]+L[HL][WL]-L[HH][WL]-L[HL][WH]
        ans=max(ans,max(cnt,N-cnt))
print(ans)

Solution (Python):




import sys
input = sys.stdin.readline

N,K=map(int,input().split())
S=[[0]*(2*K+1) for _ in range(2*K+1)]



dx=[0,0,K,2*K,K,0,-K,-2*K,-K,2*K,2*K,-2*K,-2*K]
dy=[0,2*K,K,0,-K,-2*K,-K,0,K,2*K,-2*K,2*K,-2*K]


def ch(a):
    ax=a[1]
    ay=a[0]
    if 0<=ax and ax<=2*K-1:
        if 0<=ay and ay<=2*K-1:
            return True
    return False


def ch4(a,b,c,d):
    Li=[a,b,c,d]
    for i in range(4):
        if ch(Li[i]):
            return True
    return False


def app(a):
    aa=[0,0]
    for i in range(2):
        aa[i]=a[i]
        if aa[i]<0:
            aa[i]=0
        elif aa[i]>2*K-1:
            aa[i]=2*K-1
    return aa
    

def paint(a,bw):
    S[a[0]][a[1]]+=bw
    return 0
    
    
    


for _ in range(N):
    sx,sy,sc=input().split()
    x=int(sx)%(2*K)
    y=int(sy)%(2*K)
    if sc=="W":
        bw=1
    else:
        bw=-1
        
    
    s=(x-(K-1),y-(K-1))
    for i in range(len(dx)):
        ld=[s[0]+dx[i],s[1]+dy[i]]
        ru=[ld[0]+(K-1),ld[1]+(K-1)]
        lu=[ru[0],ld[1]]
        rd=[ld[0],ru[1]]
        
        if ch4(ld,ru,lu,rd):
            ld=app(ld)
            ru=app(ru)
            ru[0]+=1
            ru[1]+=1
            lu=[ru[0],ld[1]]
            rd=[ld[0],ru[1]]
            paint(ld,bw)
            paint(ru,bw)
            paint(lu,bw*-1)
            paint(rd,bw*-1)
            
    if bw==-1:
        S[0][0]+=1
        S[-1][-1]+=1
        S[0][-1]-=1
        S[-1][0]-=1
            
            


for i in range(2*K+1):
    for j in range(2*K):
        S[i][j+1]+=S[i][j]
        
for j in range(2*K+1):
    for i in range(2*K):
        S[i+1][j]+=S[i][j]
        
        
ans=0
for i in range(2*K+1):
    for j in range(2*K+1):
        if S[i][j]>ans:
            ans=S[i][j]
          
        
print(ans)

Solution (Python):
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

N,K=map(int,input().split())
XYC=[input().split() for i in range(N)]
for i in range(N):
    x,y,c=XYC[i]
    XYC[i]=[int(x),int(y),c]

lstB=[[0 for i in range(K)] for m in range(K)]
lstW=[[0 for i in range(K)] for m in range(K)]
for x,y,c in XYC:

    if ((x//K + y//K) + (c=="W") * 1)%2==0:
        lstB[x%K][y%K]+=1
    else:
        lstW[x%K][y%K]+=1



sumB=[sum(lstB[x]) for x in range(K)]
sumW=[sum(lstW[x]) for x in range(K)]
ruisumB=[0]
ruisumW=[0]
for i in range(0,K):
    ruisumB.append(ruisumB[i]+sumB[i])
    ruisumW.append(ruisumW[i]+sumW[i])


ruiBy=[[0] for k in range(K)]
ruiWy=[[0] for k in range(K)]
for y in range(K):
    for x in range(K):
        ruiBy[y].append(lstB[x][y]+ruiBy[y][x])
        ruiWy[y].append(lstW[x][y]+ruiWy[y][x])
Revalue=0
for x in range(K+1):
    value=0
    value+=ruisumW[x]
    value+=ruisumB[K]-ruisumB[x]
    Revalue=max(Revalue,value)
    for y in range(K):
        value+=ruiWy[y][K]-2*ruiWy[y][x]
        value-=ruiBy[y][K]-2*ruiBy[y][x]
        Revalue=max(Revalue,value)

for x in range(K+1):
    value=0
    value+=ruisumB[x]
    value+=ruisumW[K]-ruisumW[x]
    Revalue=max(Revalue,value)
    for y in range(K):
        value+=ruiBy[y][K]-2*ruiBy[y][x]
        value-=ruiWy[y][K]-2*ruiWy[y][x]
        Revalue=max(Revalue,value)

print(Revalue)

Solution (Python):
import sys
import numpy as np
from collections import Counter

read = sys.stdin

N, K = map(int, read.readline().split())
k = 2 * K
xyc = np.array(read.read().split(), np.str).reshape(-1, 3)
x = xyc[:, 0].astype(int)
y = xyc[:, 1].astype(int)
c = xyc[:, 2]

x[c == 'B'] -= K
x %= k
y %= k

'''



xy, cnt = np.unique(x + y * 10000, return_counts=True)
x = xy % 10000
y = xy // 10000
'''
xy = Counter(zip(x.tolist(), y.tolist()))
cnt = np.array(list(xy.values()), np.int64)
xy = np.array(list(xy.keys()), np.int64)
x = xy[:, 0]
y = xy[:, 1]

grid = np.zeros((3 * K, 3 * K), np.int64)
grid[x, y] += cnt
grid[x + K, y + K] += cnt
grid[x + K, y] -= cnt
grid[x, y + K] -= cnt
np.cumsum(grid, axis=0, out=grid)
np.cumsum(grid, axis=1, out=grid)

p1 = grid[:K, :K] + grid[k:, k:] + grid[K:k, K:k] + grid[k:, :K] + grid[:K, k:]
p2 = grid[K:k, :K] + grid[K:k, k:] + grid[:K, K:k] + grid[k:, K:k]
print(max(p1.max(), p2.max()))

Solution (Python):
import sys
import numpy as np
from collections import Counter

read = sys.stdin

N, K = map(int, read.readline().split())
k = 2 * K
xyc = np.array(read.read().split(), np.str).reshape(-1, 3)
x = xyc[:, 0].astype(int)
y = xyc[:, 1].astype(int)
c = xyc[:, 2]

x[c == 'B'] -= K
x %= k
y %= k

'''



xy, cnt = np.unique(x + y * 10000, return_counts=True)
x = xy % 10000
y = xy // 10000
'''
xy = Counter(zip(x, y))
cnt = np.array(list(xy.values()), np.int64)
xy = np.array(list(xy.keys()), np.int64)
x = xy[:, 0]
y = xy[:, 1]

grid = np.zeros((3 * K, 3 * K), np.int64)
grid[x, y] += cnt
grid[x + K, y + K] += cnt
grid[x + K, y] -= cnt
grid[x, y + K] -= cnt
np.cumsum(grid, axis=0, out=grid)
np.cumsum(grid, axis=1, out=grid)

p1 = grid[:K, :K] + grid[k:, k:] + grid[K:k, K:k] + grid[k:, :K] + grid[:K, k:]
p2 = grid[K:k, :K] + grid[K:k, k:] + grid[:K, K:k] + grid[k:, K:k]
print(max(p1.max(), p2.max()))

Solution (Python):
import sys
import numpy as np
from collections import Counter

read = sys.stdin

N, K = map(int, read.readline().split())
k = 2 * K
xyc = np.array(read.read().split(), np.str).reshape(-1, 3)
x = xyc[:, 0].astype(int)
y = xyc[:, 1].astype(int)
c = xyc[:, 2]

x = np.where(c == 'B', x - K, x)
x %= k
y %= k

'''



xy, cnt = np.unique(x + y * 10000, return_counts=True)
x = xy % 10000
y = xy // 10000
'''
xy = Counter(list(zip(x, y)))
cnt = np.array(list(xy.values()), np.int64)
xy = np.array(list(xy.keys()), np.int64)
x = xy[:, 0]
y = xy[:, 1]

grid = np.zeros((3 * K, 3 * K), np.int64)
grid[x, y] += cnt
grid[x + K, y + K] += cnt
grid[x + K, y] -= cnt
grid[x, y + K] -= cnt
np.cumsum(grid, axis=0, out=grid)
np.cumsum(grid, axis=1, out=grid)

p1 = grid[:K, :K] + grid[k:, k:] + grid[K:k, K:k] + grid[k:, :K] + grid[:K, k:]
p2 = grid[K:k, :K] + grid[K:k, k:] + grid[:K, K:k] + grid[k:, K:k]
print(max(p1.max(), p2.max()))

Solution (Python):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
ps = []
table = [[0] * (2 * K) for _ in range(2 * K)]
res = 0
ws = 0
for i in range(N):
  u, v, t = input().split()
  u = int(u)
  v = int(v)
  ps.append((u % (2 * K), v % (2 * K), t))
  table[u % (2 * K)][v % (2 * K)] += (-1) ** int(t == "W")
  table[(u + K) % (2 * K)][(v + K) % (2 * K)] += (-1) ** int(t == "W")
  ws += (t == "W")

cs = [[0] * (2 * K + 1) for _ in range(2 * K)]
for i in range(2 * K):
  for j in range(2 * K): cs[i][j + 1] = cs[i][j] + table[i][j]

for i in range(2 * K):
  t = 0
  tres = 0
  for j in range(K): t += cs[j][min(2 * K, i + K)] + cs[j][max(0, i - K)] - cs[j][i] 
  tres = max(tres, t + ws)
  for j in range(2 * K):
    t -= cs[j][min(2 * K, i + K)] + cs[j][max(0, i - K)] - cs[j][i]
    t += cs[(j + K) % (2 * K)][min(2 * K, i + K)] + cs[(j + K) % (2 * K)][max(0, i - K)] - cs[(j + K) % (2 * K)][i]
    tres = max(tres, t + ws)
    
  res = max(res, tres)
print(res)

Solution (Python):
n,k = map(int, input().split())
g = [[0]*(k+1) for _ in range(k+1)]
ans,b = 0,0
for _ in range(n):
  x,y,c = input().split()
  x,y = int(x), int(y)
  d = x//k + y//k
  x %= k; y %= k
  if (c == 'W') ^ (d%2):
    g[x+1][y+1] += 1
  else:
    g[x+1][y+1] -= 1
    b += 1
for i in range(k):
  for j in range(k):
    g[i+1][j+1] += g[i][j+1] + g[i+1][j] - g[i][j]
for i in range(k):
  for j in range(k):
    cur = g[k][k] - g[k][j] - g[i][k] + g[i][j]*2 + b
    if cur > ans: ans = cur
    if n-cur > ans: ans = n-cur
print(ans)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    
    imos2d = [[0]*(2*K+1) for _ in range(2*K+1)]
    
    def get_cord(x):
        if x<K-1:
            return [(0,x+1), (x+K+1,2*K)]
        else:
            return [(x-K+1,x+1)]

    for _ in range(N):
        x,y,c = ST().split()
        x,y = int(x), int(y)
        if c=="W":
            x+=K
        x,y = x%(2*K), y%(2*K)
        for base in [0,K]:
            for l,r in get_cord((x+base)%(2*K)):
                for u,d in get_cord((y+base)%(2*K)):
                    imos2d[l][u] += 1
                    imos2d[l][d] -= 1
                    imos2d[r][u] -= 1
                    imos2d[r][d] += 1

    for i in range(2*K):
        for j in range(2*K+1):
            imos2d[i+1][j] += imos2d[i][j]
    
    for i in range(2*K+1):
        for j in range(2*K):
            imos2d[i][j+1] += imos2d[i][j]


    ans = 0
    for a in imos2d:
        ans = max(ans,max(a))
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import copy
from datetime import datetime


n,k = map(int ,input().split())
p = [[0] * (2*k) for i in range(2*k)]
ans = 0
for i in range(n):
  x,y,c = input().split()
  x = int(x)
  y = int(y)
  if c == 'B':
    x += k
  p[x%(2*k)][y%(2*k)] += 1




csum1 = [[0]*(2*k) for i in range(2*k)]

for i in range(2*k):
    for j in range(0, k):
        csum1[i][0] += p[i][j]
    for j in range(1, 2*k):
        csum1[i][j] = csum1[i][j-1] - p[i][j-1] + p[i][(j+k-1)%(2*k)]




csum2 = [[0]*(2*k) for i in range(2*k)]


for j in range(2*k):
    for i in range(0, k):
        csum2[0][j] += csum1[i][j]
    for i in range(1, 2*k):
        csum2[i][j] = csum2[i-1][j] - csum1[i-1][j] + csum1[(i+k-1)%(2*k)][j]



for i in range(2*k):
    for j in range(2*k):
        ans = max(ans, csum2[i][j] + csum2[(i+k)%(2*k)][(j+k)%(2*k)])

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
white = [[0]*(K+1) for _ in range(2*K+1)]
black = [[0]*(K+1) for _ in range(2*K+1)]
for _ in range(N):
    str_h, str_w, c = map(str, input().rstrip().split())
    h = int(str_h)%(2*K)
    w = int(str_w)%(2*K)
    if c == "W":
        if w >= K:
            if h >= K:
                white[h-K+1][w-K+1] += 1
            else:
                white[h+K+1][w-K+1] += 1
        else:
            white[h+1][w+1] += 1
    else:
        if w >= K:
            if h >= K:
                black[h-K+1][w-K+1] += 1
            else:
                black[h+K+1][w-K+1] += 1
        else:
            black[h+1][w+1] += 1

for h in range(1, 2*K+1):
    for w in range(1, K+1):
        white[h][w] += white[h][w-1] + white[h-1][w] - white[h-1][w-1]
        black[h][w] += black[h][w-1] + black[h-1][w] - black[h-1][w-1]

ans = 0
for h in range(K+1):
    for w in range(K+1):
        b1 = black[h][w]
        b2 = black[h+K][K] - black[h+K][w] - black[h][K] + black[h][w]
        b3 = black[2*K][w] - black[h+K][w]
        w1 = white[h][K] - white[h][w]
        w2 = white[h+K][w] - white[h][w]
        w3 = white[2*K][K] - white[2*K][w] - white[h+K][K] + white[h+K][w]
        ans = max(ans, b1+b2+b3+w1+w2+w3)

        b1 = white[h][w]
        b2 = white[h+K][K] - white[h+K][w] - white[h][K] + white[h][w]
        b3 = white[2*K][w] - white[h+K][w]
        w1 = black[h][K] - black[h][w]
        w2 = black[h+K][w] - black[h][w]
        w3 = black[2*K][K] - black[2*K][w] - black[h+K][K] + black[h+K][w]
        ans = max(ans, b1+b2+b3+w1+w2+w3)

print(ans)

Solution (Python):
class Acc2D:
    def __init__(self, a):
        h, w = len(a), len(a[0])
        self.acc2D = self._build(h, w, a)

    def _build(self, h, w, a):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r][c + 1] + ret[r + 1][c] - ret[r][c] + a[r][c]
                
        return ret

    def get(self, r1, r2, c1, c2):
        
        acc2D = self.acc2D
        return acc2D[r2][c2] - acc2D[r1][c2] - acc2D[r2][c1] + acc2D[r1][c1]


def main():
    import sys

    input = sys.stdin.readline

    n, k = map(int, input().split())

    g = [[0] * (k * 2) for _ in range(k * 2)]
    for _ in range(n):
        x, y, c_ = input().split()
        x = int(x) % (k * 2)
        y = int(y) % (k * 2)
        if c_ == 'W':
            y = (y + k) % (k * 2)
            
        g[y][x] += 1  

    acc2D = Acc2D(g)

    ret = 0
    
    
    for r in range(k):  
        for c in range(k):  
            s = (
                    acc2D.get(0, r, 0, c)
                    + acc2D.get(0, r, c + k, k * 2)
                    + acc2D.get(r, r + k, c, c + k)
                    + acc2D.get(r + k, k * 2, 0, c)
                    + acc2D.get(r + k, k * 2, c + k, k * 2)
            )
            ret = max(ret, s, n - s)

    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

N, K = map(int, input().split())
K2 = K*2

M = np.zeros((K2, K2), int)
nb = 0
for _ in range(N):
  x, y, c = input().split()
  x = int(x) % K2
  y = int(y) % K2
  if c=='B': nb+=1
  M[x, y] += 1 if c=='W' else -1

Sx = np.zeros((K2, K2+1), int)
for y in range(K2):
  Sx[:, y+1] = Sx[:, y] + M[:, y]

S = np.zeros((K2+1, K2+1), int)
for x in range(K2):
  S[x+1] = S[x] + Sx[x]

ans = -1000000
for x in range(K2):
  x0 = 0
  x1 = max(x-K , 0)
  x2 = x
  x3 = min(x+K , K2)
  x4 = K2

  T1 = S[x4] - S[x3] + S[x2] - S[x1]
  T2 = S[x3] - S[x2] + S[x1] - S[x0]

  U = T1[K2] - T1[K:K2] + T1[:K] + T2[K:K2] - T2[:K]
  ans = max(ans, np.max(U))
  
print(nb + ans)

Solution (Python):
n, k = map(int, input().split())
imos = [[0 for i in range(k)] for j in range(k)]
white = 0
for i in range(n):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == "W":
        c = 1
    else:
        c = 0
    x %= 2*k
    y %= 2*k

    if x > k-1:
        x -= k
        c += 1
    if y > k-1:
        y -=k
        c += 1
    c %= 2

    if c == 1:
        white += 1
        imos[x][y] -= 1
    else:
        imos[x][y] += 1

for i in range(k):
    for j in range(k-1):
        imos[i][j+1] += imos[i][j]

for j in range(k):
    for i in range(k-1):
        imos[i+1][j] += imos[i][j]

ans = 0
for i in range(k):
    for j in range(k):
        exp = imos[k-1][k-1] - imos[k-1][j] - imos[i][k-1] + 2 * imos[i][j] + white
        ans = max(ans, max(exp, n - exp))

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

def query(x1, y1, x2, y2, acc):
    return acc[x2+1][y2+1]-acc[x2+1][y1]-acc[x1][y2+1]+acc[x1][y1]

N, K = map(int, input().split())
W = [[0]*K for _ in range(K)]
B = [[0]*K for _ in range(K)]

for _ in range(N):
    xi, yi, ci = input().split()
    xi = int(xi)
    yi = int(yi)
    t = (xi-xi%K)//K+(yi-yi%K)//K
    
    if t%2==1:
        ci = 'B' if ci=='W' else 'W'
    
    if ci=='W':
        W[xi%K][yi%K] += 1
    else:
        B[xi%K][yi%K] += 1


W_acc = [[0]*(K+1) for _ in range(K+1)]
B_acc = [[0]*(K+1) for _ in range(K+1)]

for i in range(K):
    for j in range(K):
        W_acc[i+1][j+1] = W_acc[i+1][j]+W_acc[i][j+1]-W_acc[i][j]+W[i][j]
        B_acc[i+1][j+1] = B_acc[i+1][j]+B_acc[i][j+1]-B_acc[i][j]+B[i][j]
        
ans = 0

for i in range(K):
    for j in range(K):
        clear_w = query(0, 0, i, j, W_acc)+query(i+1, j+1, K-1, K-1, W_acc)
        clear_b = query(i+1, 0, K-1, j, B_acc)+query(0, j+1, i, K-1, B_acc)
        ans = max(ans, clear_w+clear_b)
        
        clear_w = query(0, 0, i, j, B_acc)+query(i+1, j+1, K-1, K-1, B_acc)
        clear_b = query(i+1, 0, K-1, j, W_acc)+query(0, j+1, i, K-1, W_acc)
        ans = max(ans, clear_w+clear_b)
        
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N,K=map(int,input().split())

lis=[[[0]*K for _ in range(K)] for i in range(2)]
for i in range(N):
    x,y,c=input().split()
    x=int(x)
    y=int(y)
    """x.append(int(xx))
    y.append(int(yy))
    c.append(cc)"""
    if c=="B" :
        C=1
    if c=="W":
        C=0
    now=(x//K+y//K+C)%2
    lis[now][x%K][y%K]+=1

for t in range(2):
    for i in range(K):
        for j in range(1,K):
            lis[t][i][j]+=lis[t][i][j-1]
    
    for i in range(1,K):
        for j in range(K):
            lis[t][i][j]+=lis[t][i-1][j]
            
"""for t in range(2):
    for i in range(K):
        for j in range(K):
            if i!=0 : lis[t][i][j]+=lis[t][i-1][j]
            if j!=0 : lis[t][i][j]+=lis[t][i][j-1]
            if i!=0 and j!=0:
                lis[t][i][j]-=lis[t][i-1][j-1]"""

ans=0
for t in range(2):
    for i in range(K):
        for j in range(K):
            cnt=2*lis[t][i][j]+lis[t][-1][-1]-lis[t][i][-1]-lis[t][-1][j]\
            +lis[1-t][i][-1]+lis[1-t][-1][j]-2*lis[1-t][i][j]
            ans=max(ans,cnt)
"""
for i in range(K):
    for j in range(K):
        cnt=-2*lis[i][j]+lis[i][-1]+lis[-1][j]
        ans=max(ans,cnt)"""

print(ans)

Solution (Python):


def main():
    import sys

    input = sys.stdin.readline

    N, K = map(int, input().split())

    grid = [[0] * (K * 2) for _ in range(K * 2)]
    for _ in range(N):
        col, row, color = input().split()
        col = int(col)
        row = int(row)
        if color == 'W':
            row += K
            
        row %= K * 2
        col %= K * 2
        grid[row][col] += 1

    tbl = [[0] * (K * 2 + 1) for _ in range(K * 2 + 1)]
    for row in range(K * 2):
        for col in range(K * 2):
            tbl[row + 1][col + 1] = tbl[row + 1][col] + tbl[row][col + 1] - tbl[row][col] + grid[row][col]

    def count(row, col, row2, col2):
        return tbl[row2][col2] - tbl[row][col2] - tbl[row2][col] + tbl[row][col]

    ret = 0
    for row in range(K):
        for col in range(K):
            tmp = (
                    count(0, 0, row, col)
                    + count(row, col, row + K, col + K)
                    + count(row + K, col + K, K * 2, K * 2)
                    + count(row + K, 0, K * 2, col)
                    + count(0, col + K, row, K * 2)
            )
            ret = max(ret, tmp, N - tmp)
            
            
            
            
            

    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
from numpy import*
N,K=map(int,input().split())
m=zeros((3*K,3*K),dtype=int)
L=2*K
o=0
for _ in [0]*N:
 x,y,c=input().split()
 x,y=int(x)%L,int(y)%L
 t=c=='W'
 m[x,y]+=2*t-1
 o+=t
for _ in [0,0]:
 m[L:]=m[:K]
 m=cumsum(m,axis=0)
 m[:L]-=m[K:]
 m=m.T
m=m[:L,:L]
print(o-int((m+roll(roll(m,K,axis=0),K,axis=1)).min()))

Solution (Python):
def main():
    from itertools import accumulate as ac
    n,k=map(int,input().split())
    kk=2*k
    xyc=[input().split() for _ in [0]*n]
    b=[[0]*(k+1) for _ in [0]*(kk+1)]
    for x,y,c in xyc:
        if c=="B":
            if int(y)%kk<k:
                b[int(x)%kk+1][int(y)%k+1]+=1
            else:
                b[(int(x)+k)%kk+1][int(y)%k+1]+=1
        else:
            if int(y)%kk<k:
                b[(int(x)+k)%kk+1][int(y)%k+1]+=1
            else:
                b[int(x)%kk+1][int(y)%k+1]+=1
    b=[list(ac(i)) for i in b]
    for i in range(1,kk+1):
        for j in range(k+1):
            b[i][j]+=b[i-1][j]
    ans=0
    for i in range(kk):
        if i==0:
            a_t=((i,i+k,0),(i+k,kk,1))
        elif i<k:
            a_t=((0,i,-1),(i,i+k,0),(i+k,kk,1))
        elif i==k:
            a_t=((0,i,-1),(i,kk,0))
        else:
            a_t=((0,i-k,-2),(i-k,i,-1),(i,kk,0))
        for j in range(k):
            if j==0:
                b_t=((0,k,0),)
            else:
                b_t=((0,j,-1),(j,k,0))
            black=[]
            for i,j,l in a_t:
                for x,y,z in b_t:
                    if (l+z)%2==0:
                        black.append((i,x,j,y))
            ret=0
            for tx1,ty1,tx2,ty2 in black:
                ret+=b[tx1][ty1]+b[tx2][ty2]-b[tx1][ty2]-b[tx2][ty1]
            ans=max(ans,ret)
    print(ans)
main()

Solution (Python):
class twoD_cumsum():
    
    def __init__(self,h,w,a):
        self.h = h; self.w = w
        self.da = a
        for i in range(1, w):
            self.da[0][i] = self.da[0][i - 1] + a[0][i]
        for i in range(1, h):
            cnt_w = 0
            for j in range(w):
                cnt_w += a[i][j]
                self.da[i][j] = self.da[i - 1][j] + cnt_w
    def da_generate(self, da):
        return da
    
    def da_calc(self, p, q, x, y):
        if p > x or q > y:
            return 0
        if p == 0 and q == 0:
            return self.da[x][y]
        if p == 0:
            return self.da[x][y] - self.da[x][q - 1]
        if q == 0:
            return self.da[x][y] - self.da[p - 1][y]
        return self.da[x][y] - self.da[p - 1][y] - self.da[x][q - 1] + self.da[p - 1][q - 1]

def examD():
    N, K = LI()
    
    colorXY = [[0] * (2*K) for _ in range(2*K)]
    for _ in range(N):
        
        x, y, c = LSI()
        x, y = int(x), int(y)
        if c=="B":
            y +=K
        colorXY[x%(2*K)][y%(2*K)] +=1
    ans = 0
    ansC = N
    da = twoD_cumsum(2*K, 2*K, colorXY)
    for i in range(K):
        for j in range(K):
            cur = da.da_calc(0,0,K-i-1,K-j-1) + da.da_calc(K-i,K-j,2*K-i-1,2*K-j-1)\
                + da.da_calc(0,2*K-j,K-i-1,2*K-1) + da.da_calc(2*K-i,0,2*K-1,K-j-1)\
                + da.da_calc(2*K-i,2*K-j,2*K-1,2*K-1)
            ans = max(ans,cur)
            ansC = min(ansC,cur)
    print(max(ans,N-ansC))

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Solution (Python):

def da_generate(h,w,a):
    da = [[0]*w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1,w):
        da[0][i] = da[0][i-1]+a[0][i]
    for i in range(1,h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i-1][j]+cnt_w
    return da


def da_calc(da,p,q,x,y):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y]-da[x][q-1]
    if q == 0:
        return da[x][y]-da[p-1][y]
    return da[x][y]-da[p-1][y]-da[x][q-1]+da[p-1][q-1]

def examD():
    N, K = LI()
    
    colorXY = [[0] * (2*K) for _ in range(2*K)]
    for _ in range(N):
        
        x, y, c = LSI()
        x, y = int(x), int(y)
        if c=="B":
            y +=K
        colorXY[x%(2*K)][y%(2*K)] +=1
    ans = 0
    ansC = N
    da = da_generate(2*K, 2*K, colorXY)
    for i in range(K):
        for j in range(K):
            cur = da_calc(da,0,0,K-i-1,K-j-1) + da_calc(da,K-i,K-j,2*K-i-1,2*K-j-1)\
                + da_calc(da,0,2*K-j,K-i-1,2*K-1) + da_calc(da,2*K-i,0,2*K-1,K-j-1)\
                + da_calc(da,2*K-i,2*K-j,2*K-1,2*K-1)
            ans = max(ans,cur)
            ansC = min(ansC,cur)
    print(max(ans,N-ansC))

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Solution (Python):
N, K = map(int, input().split())
X = [[0] * (2*K) for _ in range(3*K)]
for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == "B":
        x += K
    x %= 2*K
    y %= 2*K
    if y >= K:
        x, y = (x+K) % (2*K), y - K
    for dx, dy in ((0, 0), (2*K, 0), (K, K), (-K, K)):
        xx, yy = x + dx, y + dy
        if 0 <= xx < 3*K and 0 <= yy < 2*K:
            X[xx][yy] += 1

for i in range(1, 3*K):
    for j in range(2*K):
        X[i][j] += X[i-1][j]
for i in range(3*K):
    for j in range(1, 2*K):
        X[i][j] += X[i][j-1]

ma = 0
for i in range(2*K):
    for j in range(K):
        ma = max(ma, X[i+K][j+K] - X[i][j+K] - X[i+K][j] + X[i][j])
print(ma)

Solution (Python):
import sys
input = sys.stdin.readline

def cumsum_2d(inlist,h,w):
    
    outlist = [ [ inlist[i-1][j-1] if i != 0 and j != 0 else 0 for i in range(k+1) ] for j in range(k+1) ]
    for i in range(1,h+1):
        tmp = 0
        for j in range(1,w+1):
            tmp += outlist[i][j]
            outlist[i][j] = tmp
    for i in range(1,w+1):
        tmp = 0
        for j in range(1,h+1):
            tmp += outlist[j][i]
            outlist[j][i] = tmp

    return outlist
    
n, k = [ int(v) for v in input().split() ]
hope = [ [ a for a in input().split() ] for i in range(n) ]

b_board = [ [ 0 for i in range(k)] for j in range(k) ]
w_board = [ [ 0 for i in range(k)] for j in range(k) ]



for h, w, c in hope:
    a1, a2 = divmod(int(w),k)
    b1, b2 = divmod(int(h),k)
    if (a1+b1) % 2 == 1:
        if c == "B":
            c = "W"
        else:
            c = "B"

    if c == "B":
        b_board[b2][a2] += 1
    else:
        w_board[b2][a2] += 1
    
b_board_3 = cumsum_2d(b_board,k,k)
w_board_3 = cumsum_2d(w_board,k,k)


total_b, total_w = b_board_3[k][k], w_board_3[k][k]
ans = 0

for i in range(1,k+1):
    for j in range(1,k+1):
        b1 = b_board_3[i][j] - b_board_3[0][j] - b_board_3[i][0]
        b2 = total_b - b_board_3[i][k] - b_board_3[k][j] + b_board_3[i][j]
        w1 = w_board_3[i][j] - w_board_3[0][j] - w_board_3[i][0]
        w2 = total_w - w_board_3[i][k] - w_board_3[k][j] + w_board_3[i][j]
        ans = max(b1+b2+(total_w-w1-w2),w1+w2+(total_b-b1-b2),ans)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

def cumsum_2d(inlist,h,w):
    outlist = [ [ inlist[i-1][j-1] if i != 0 and j != 0 else 0 for i in range(k+1) ] for j in range(k+1) ]
    for i in range(1,h+1):
        tmp = 0
        for j in range(1,w+1):
            tmp += outlist[i][j]
            outlist[i][j] = tmp
    for i in range(1,w+1):
        tmp = 0
        for j in range(1,h+1):
            tmp += outlist[j][i]
            outlist[j][i] = tmp

    return outlist
    
n, k = [ int(v) for v in input().split() ]
hope = [ [ a for a in input().split() ] for i in range(n) ]

b_board = [ [ 0 for i in range(k)] for j in range(k) ]
w_board = [ [ 0 for i in range(k)] for j in range(k) ]



for h, w, c in hope:
    a1, a2 = divmod(int(w),k)
    b1, b2 = divmod(int(h),k)
    if (a1+b1) % 2 == 1:
        if c == "B":
            c = "W"
        else:
            c = "B"

    if c == "B":
        b_board[int(h)%k][int(w)%k] += 1
    else:
        w_board[int(h)%k][int(w)%k] += 1
    
b_board_3 = cumsum_2d(b_board,k,k)
w_board_3 = cumsum_2d(w_board,k,k)


total_b, total_w = b_board_3[k][k], w_board_3[k][k]
ans = 0

for i in range(1,k+1):
    for j in range(1,k+1):
        b1 = b_board_3[i][j] - b_board_3[0][j] - b_board_3[i][0]
        b2 = total_b - b_board_3[i][k] - b_board_3[k][j] + b_board_3[i][j]
        w1 = w_board_3[i][j] - w_board_3[0][j] - w_board_3[i][0]
        w2 = total_w - w_board_3[i][k] - w_board_3[k][j] + w_board_3[i][j]
        ans = max(b1+b2+(total_w-w1-w2),w1+w2+(total_b-b1-b2),ans)

print(ans)