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



Sample input:
4 3
0 1 W
1 2 W
5 3 B
5 4 B


Sample output:
4

Submission status: Accepted

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

A = [[ 0 for _ in range(K2) ] for _ in range(K2)]
for _ in range(N):
  x,y,c = input().split()
  x,y = int(x) % (K2), int(y) % (K2)
  if c == 'W':
    y = (y+K) % (K2)
  #if y >= K:
  #  x,y = (x+K) %K2, y-K
  A[x][y] += 1

for i in range(K2):
  A[i] = A[i]  + A[i][:K-1]
  
for i in range(K-1):
  A.append(A[i])
  
#for a in A:
#  print(a)


B = [[ 0 for _ in range(K2+K) ] for _ in range(K2+K)]
for i in range(K2+K-1):
  for j in range(K2+K-1):
    B[i+1][j+1] = B[i+1][j] + B[i][j+1] - B[i][j] + A[i][j]
    
ans = 0
for i in range(K):
  for j in range(K):
    # (i,j)(i+K-1)(j+K-1) , (i+K,j+K), (i+2k-1)(j+2k-1)
    wk = 0
    wk += B[i+K][j+K] - B[i][j+K] - B[i+K][j] + B[i][j]
    wk += B[i+K2][j+K2] - B[i+K][j+K2] - B[i+K2][j+K] + B[i+K][j+K]
    #print(i,i+K,i+K2)
    ans = max(wk,N-wk,ans) #N-wkは白黒反転させたとき
#for b in B:
#  print(b)
  
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

read=sys.stdin.read
readline=sys.stdin.readline

def main():
  wb={'W':1,'B':0}
  n,k=map(int,readline().split())
  xyc=[l.split() for l in read().splitlines()]
  xy=[[int(lst[0]) % (2*k),(int(lst[1])+k*wb[lst[2]]) % (2*k)] for lst in xyc]
  mat=np.zeros((k+1,2*k+1),dtype='int64')
  cand=np.zeros((k+1,k+1),dtype='int64')
  for e in xy:
    f0=e[0]>=k
    f1=e[1]>=k
    mat[e[0]-f0*k+1,e[1]+(-1)**f1*f0*k+1]+=1
  mat=np.cumsum(mat,axis=0)
  mat=np.cumsum(mat,axis=1)
  cand=mat[k,2*k]-mat[k,k:2*k+1]+mat[k,:k+1]\
       -np.reshape(mat[:k+1,2*k],(k+1,1))+2*mat[:,k:2*k+1]-2*mat[:,:k+1]
  print(max(np.max(cand),mat[k,2*k]-np.min(cand)))
  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import numpy as np
N, K, *XYC = open(0).read().split()
N = int(N)
K = int(K)
board = np.zeros((4 * K + 1, 4 * K + 1), dtype=np.int64)
for x, y, c in zip(XYC[::3], XYC[1::3], XYC[2::3]):
    x = int(x)
    y = int(y)
    if c == 'W':
        x += K
    x = x % (2 * K)
    y = y % (2 * K)
    board[x, y] += 1
    board[(x + K) % (2 * K), (y + K) % (2 * K)] += 1
board[1 + 2 * K:, 1 + 2 * K:] = board[:2 * K, :2 * K]
board[1:1 + 2 * K, 1 + 2 * K:] = board[1 + 2 * K:, 1 + 2 * K:]
board[1 + 2 * K:, 1:1 + 2 * K] = board[1 + 2 * K:, 1 + 2 * K:]
board[1:1 + 2 * K, 1:1 + 2 * K] = board[1 + 2 * K:, 1 + 2 * K:]
board[0, :] = 0
board[:, 0] = 0
for j in range(1, 3 * K):
    board[:, j] += board[:, j - 1]
for j in range(1, 3 * K):
    board[j, :] += board[j - 1, :]
ans = np.max(board[K:3 * K, K:3 * K] + board[:2 * K, :2 * K] -
             board[:2 * K, K:3 * K] - board[K:3 * K, :2 * K])
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
N, K, *XYC = open(0).read().split()
N = int(N)
K = int(K)
board = np.zeros((4 * K + 1, 4 * K + 1), dtype=np.uint16)
for x, y, c in zip(XYC[::3], XYC[1::3], XYC[2::3]):
    x = int(x)
    y = int(y)
    if c == 'W':
        x += K
    x = x % (2 * K)
    y = y % (2 * K)
    board[x, y] += 1
    board[(x + K) % (2 * K), (y + K) % (2 * K)] += 1
board[1 + 2 * K:, 1 + 2 * K:] = board[:2 * K, :2 * K]
board[1:1 + 2 * K, 1 + 2 * K:] = board[1 + 2 * K:, 1 + 2 * K:]
board[1 + 2 * K:, 1:1 + 2 * K] = board[1 + 2 * K:, 1 + 2 * K:]
board[1:1 + 2 * K, 1:1 + 2 * K] = board[1 + 2 * K:, 1 + 2 * K:]
board[0, :] = 0
board[:, 0] = 0
for j in range(1, 3 * K):
    board[:, j] += board[:, j - 1]
for j in range(1, 3 * K):
    board[j, :] += board[j - 1, :]
ans = np.max(board[K:3 * K, K:3 * K] + board[:2 * K, :2 * K] -
             board[:2 * K, K:3 * K] - board[K:3 * K, :2 * K])
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
N, K, *XYC = open(0).read().split()
N = int(N)
K = int(K)
board = np.zeros((4 * K + 1, 4 * K + 1), dtype=np.uint16)
for x, y, c in zip(XYC[::3], XYC[1::3], XYC[2::3]):
    x = int(x)
    y = int(y)
    if c == 'W':
        x += K
    x = x % (2 * K)
    y = y % (2 * K)
    board[x, y] += 1
    board[(x + K) % (2 * K), (y + K) % (2 * K)] += 1
board[1 + 2 * K:, 1 + 2 * K:] = board[:2 * K, :2 * K]
board[1:1 + 2 * K, 1 + 2 * K:] = board[1 + 2 * K:, 1 + 2 * K:]
board[1 + 2 * K:, 1:1 + 2 * K] = board[1 + 2 * K:, 1 + 2 * K:]
board[1:1 + 2 * K, 1:1 + 2 * K] = board[1 + 2 * K:, 1 + 2 * K:]
board[0, :] = 0
board[:, 0] = 0
for j in range(1, 1 + 4 * K):
    board[:, j] += board[:, j - 1]
for j in range(1, 1 + 4 * K):
    board[j, :] += board[j - 1, :]
ans = np.max(board[K:3 * K, K:3 * K] + board[:2 * K, :2 * K] -
             board[:2 * K, K:3 * K] - board[K:3 * K, :2 * K])
print(ans)

Submission status: Accepted

Solution code:
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();t=c=='W';m[int(x)%L,int(y)%L]+=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()))

Submission status: Accepted

Solution code:
n,k=map(int,input().split());m=2*k;a=[(m+1)*[0]for _ in[0]*(m+1)];z=lambda i,j:(a[i][j]-a[i-k][j]-a[i][j-k]+a[i-k][j-k])*2+a[m][m]-a[i][m]-a[m][j]+a[i-k][m]+a[m][j-k]
for _ in[0]*n:x,y,c=input().split();x=int(x);y=int(y)+k*(c=="B");a[x%m+1][y%m+1]+=1
for i in range(m):
  for j in range(m):a[i+1][j+1]+=a[i][j+1]+a[i+1][j]-a[i][j]
print(max(max(max(z(i,j),n-z(i,j))for j in range(k,m+1))for i in range(k,m+1)))

Submission status: Accepted

Solution code:
def cumsum_2d(arr, cumsum_from='top_left'):
    K = len(arr)  # arr: K * K array
    ret = [[0 for _ in range(K)] for _ in range(K)]
    # 行方向に累積和
    for y in range(K):
        v = 0
        for x in range(K):
            if 'right' in cumsum_from:
                x = K - 1 - x
            v += arr[y][x]
            ret[y][x] = v
    # 列方向に累積和
    for y in range(1, K):
        before_y = y - 1
        if 'bottom' in cumsum_from:
            y = K - 1 - y
            before_y = y + 1
        for x in range(K):
            ret[y][x] += ret[before_y][x]
    return ret


def main():
    N, K = list(map(int, input().split()))
    # 同じ色になるセルをひとまとめにする
    field_even = [[0 for _ in range(K)] for _ in range(K)]
    field_odd = [[0 for _ in range(K)] for _ in range(K)]
    for _ in range(N):
        X, Y, C = input().split()
        X = int(X) - 1
        Y = int(Y) - 1
        white_flag = 1 if C == 'W' else 0
        score = X // K + Y // K + white_flag
        if score % 2 == 0:
            field_even[Y % K][X % K] += 1
        else:
            field_odd[Y % K][X % K] += 1
    # 右上・右下・左上・左下からの2次元累積和
    even_tr = cumsum_2d(field_even, 'top_right')
    even_br = cumsum_2d(field_even, 'bottom_right')
    even_tl = cumsum_2d(field_even, 'top_left')
    even_bl = cumsum_2d(field_even, 'bottom_left')
    odd_tr = cumsum_2d(field_odd, 'top_right')
    odd_br = cumsum_2d(field_odd, 'bottom_right')
    odd_tl = cumsum_2d(field_odd, 'top_left')
    odd_bl = cumsum_2d(field_odd, 'bottom_left')
    # K * Kの正方形内の分割方法を全通り試して答えを求める
    # 分割のうち、左上の正方形の右下のセルの座標で場合分け
    ans = 0
    for y in range(-1, K):
        for x in range(-1, K):
            # pattern 1
            c = 0
            if y >= 0 and x >= 0:
                c += even_tl[y][x]
            if y + 1 < K and x + 1 < K:
                c += even_br[y + 1][x + 1]
            if y + 1 < K and x >= 0:
                c += odd_bl[y + 1][x]
            if y >= 0 and x + 1 < K:
                c += odd_tr[y][x + 1]
            ans = max(ans, c)
            # pattern 2(oddとeven入れ替え（白黒反転）)
            c = 0
            if y >= 0 and x >= 0:
                c += odd_tl[y][x]
            if y + 1 < K and x + 1 < K:
                c += odd_br[y + 1][x + 1]
            if y + 1 < K and x >= 0:
                c += even_bl[y + 1][x]
            if y >= 0 and x + 1 < K:
                c += even_tr[y][x + 1]
            ans = max(ans, c)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K=map(int, input().split())
A=[[0]*(2*K) for j in range(2*K)]
for i in range(N):
  x,y,a=input().split()
  x,y=int(x),int(y)
  if a=='B':
    y+=K
  x=x%(2*K)
  y=y%(2*K)
  A[y][x]+=1
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

#da_calc(p,q,x,y):(p,q)~(x,y)の長方形の和
def da_calc(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]
f=2*K
da=da_generate(f,f,A)
ans=0
for i in range(K+1):
  for j in range(K+1):
    a=da_calc(j,i,j+K-1,i+K-1)   
    y1,y2,x1,x2=i,i+K-1,j,j+K-1
    if x1>0 and y1>0:
      a+=da_calc(0,0,x1-1,y1-1)
    if x1>0 and y2<f:
      a+=da_calc(0,y2+1,x1-1,f-1)
    if x2<f and y1>0:
      a+=da_calc(x2+1,0,f-1,y1-1)
    if x2<f and y2<f:
      a+=da_calc(x2+1,y2+1,f-1,f-1)
    ans=max(ans,a,N-a)
print(ans)

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()

N,K = MI()

black = [[0]*K for _ in range(K)]
white = [[0]*K for _ in range(K)]
for _ in range(N):
    x,y,c = map(str,S().split())
    x,y = int(x),int(y)
    if ((x//K + y//K) % 2 == 0 and c == 'B') or ((x//K + y//K) % 2 == 1 and c == 'W'):
        black[x % K][y % K] += 1
    else:
        white[x % K][y % K] += 1

black_accumulate = [[0]*(K+1)] + [[0]+black[i] for i in range(K)]  # black の2次元累積和
white_accumulate = [[0]*(K+1)] + [[0]+white[i] for i in range(K)]  # white の2次元累積和
for i in range(1,K+1):
    for j in range(1,K+1):
        black_accumulate[i][j] += black_accumulate[i][j-1]
        white_accumulate[i][j] += white_accumulate[i][j-1]
for i in range(1,K+1):
    for j in range(1,K+1):
        black_accumulate[i][j] += black_accumulate[i-1][j]
        white_accumulate[i][j] += white_accumulate[i-1][j]

def f(s,t,u,v):  # black の (s,t]×(u,v] の区間和
    return black_accumulate[t][v]-black_accumulate[t][u]-black_accumulate[s][v]+black_accumulate[s][u]
def g(s,t,u,v):  # white の (s,t]×(u,v] の区間和
    return white_accumulate[t][v]-white_accumulate[t][u]-white_accumulate[s][v]+white_accumulate[s][u]

ans = 0
for i in range(1,K+1):  # 区切る位置
    for j in range(1,K+1):  # 区切る位置
        ans = max(ans,f(0,i,0,j) + f(i,K,j,K) + g(0,i,j,K) + g(i,K,0,j))
        ans = max(ans,g(0,i,0,j) + g(i,K,j,K) + f(0,i,j,K) + f(i,K,0,j))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
 
N,K=map(int, input().split())
p=[list(input().split()) for _ in range(N)]
grid = [[[0]*2 for j in range(K)] for i in range(K)]

for i in range(N):
  x, y, c = p[i]
  x, y = int(x), int(y)
  mx, my = x%K, y%K
  f = False
  if (x//K)%2 != (y//K)%2:
    f = not f
  if c == "W":
    f = not f
  if f:
    grid[0][0][0] += 1
    grid[mx][0][0] -= 1
    grid[0][my][0] -= 1
    grid[mx][my][0] += 2
  else:
    grid[0][my][0] += 1
    grid[mx][0][0] += 1
    grid[mx][my][0] -= 2
  f = False
  if (x//K)%2 != (y//K)%2:
    f = not f
  if c == "B":
    f = not f
  if f:
    grid[0][0][1] += 1
    grid[mx][0][1] -= 1
    grid[0][my][1] -= 1
    grid[mx][my][1] += 2
  else:
    grid[0][my][1] += 1
    grid[mx][0][1] += 1
    grid[mx][my][1] -= 2
grid = np.array(grid)
grid = np.cumsum(grid, axis=0)
grid = np.cumsum(grid, axis=1)
print(int(np.max(grid)))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

n, k = getNM()
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)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
g=[[[0,0] for i in range(k)] for j in range(k)]

for i in range(n):
    x,y,c=input().split()
    x,y=int(x),int(y)
    if y%(2*k)<k and x%(2*k)<k:
        g[y%(2*k)][x%(2*k)][c=="W"]+=1
    elif y%(2*k)<k:
        g[y%(2*k)][x%(2*k)-k][c=="B"]+=1
    elif x%(2*k)<k:
        g[y%(2*k)-k][x%(2*k)][c=="B"]+=1
    else:
        g[y%(2*k)-k][x%(2*k)-k][c=="W"]+=1

ac=[[[0]*(k+1) for i in range(k+1)] for l in range(2)]
for l in range(2):
    for i in range(k):
        for j in range(k):
            ac[l][i+1][j+1]=ac[l][i][j+1]+ac[l][i+1][j]-ac[l][i][j]+g[i][j][l]

ans=0
for i in range(k):
    for j in range(k):
        ans=max(ac[0][k][k]-ac[0][i][k]-ac[0][k][j]+2*ac[0][i][j]+ac[1][i][k]+ac[1][k][j]-2*ac[1][i][j],ans)
        ans=max(ac[1][k][k]-ac[1][i][k]-ac[1][k][j]+2*ac[1][i][j]+ac[0][i][k]+ac[0][k][j]-2*ac[0][i][j],ans)
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
square = [[0 for i in range(k*2)] for j in range(k*2)]
 
for i in range(n):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c=='W':
        y += k
    x = x%(k*2)
    y = y%(k*2)
    square[x][y] += 1
 
class CumulativeSum2d():
    def __init__(self, collection_2d):
        yl = len(collection_2d)
        xl = len(collection_2d[0])
        self.data = [[0] * (xl+1) for _ in range(yl+1)]
        for y in range(1, yl+1):
            for x in range(1, xl+1):
                top_sum         = self.data[y-1][x]
                left_sum        = self.data[y][x-1]
                dup_sum         = self.data[y-1][x-1]
                self.data[y][x] = top_sum + left_sum - dup_sum
                self.data[y][x] += collection_2d[y-1][x-1]
 
    def query(self, x, y, x1, y1):
        return self.data[y1][x1] - self.data[y-1][x1] - self.data[y1][x-1] + self.data[y-1][x-1]
 
cs = CumulativeSum2d(square)
 
"""
xxxxxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx
 
oxxxoo
oxxxoo
oxxxoo
xoooxx
xoooxx
xoooxx
 
0xxxoo
x000xx
x000xx
x000xx
0xxxoo
0xxxoo
 
xoooxx
oxxxoo
oxxxoo
oxxxoo
xoooxx
xoooxx
 
1 k  2k
xxxooo
xxxooo
xxxooo
000xxx
000xxx
000xxx
 
          1xk  2k
         10xxxoo
         yx000xx
         kx000xx
          x000xx
          0xxxoo
        2k0xxxoo
 
left top position determine everything
"""
ans = 0
for x in range(1,k*2+1):
    for y in range(1,k*2+1):
        sumd = 0
        # main_area
        sumd += cs.query(x, y, min(k*2, x+k-1), min(k*2, y+k-1))
        """
        """
        if x-k>1:
            # left_area
            sumd += cs.query(1, y, x-k-1, min(k*2, y+k-1))
        if y-k>1:
            # top_area
            sumd += cs.query(x, 1, min(k*2, x+k-1), y-k-1)
        if x>1 and y>1:
            # left_top_area
            sumd += cs.query(max(1, x-k), max(1, y-k), x-1, y-1)
        if x>1 and y-k<1:
            # left_bottom_area
            sumd += cs.query(max(1, x-k), y+k, x-1, k*2)
        if x-k<1 and y>1:
            # right_top_area
            sumd += cs.query(x+k, max(1, y-k), k*2, y-1)
        if x-k<1 and y-k<1:
            # right_bottom_area
            sumd += cs.query(x+k, y+k, k*2, k*2)
        ans = max(sumd, ans)
 
print(ans , flush=True)

Submission status: Accepted

Solution code:
import numpy as np

def main():
    n, k = map(int, input().split())
    p = [list(map(str, input().split())) for _ in range(n)]
    arr = [[[0]*2 for j in range(k)] for i in range(k)]
    for i in range(n):
        x, y, c = p[i]
        x, y = int(x), int(y)
        mx, my = x%k, y%k
        f = False
        if (x//k)%2 != (y//k)%2:
            f = not f
        if c == "W":
            f = not f
        if f:
            arr[0][0][0] += 1
            arr[mx][0][0] -= 1
            arr[0][my][0] -= 1
            arr[mx][my][0] += 2
        else:
            arr[0][my][0] += 1
            arr[mx][0][0] += 1
            arr[mx][my][0] -= 2
        f = False
        if (x//k)%2 != (y//k)%2:
            f = not f
        if c == "B":
            f = not f
        if f:
            arr[0][0][1] += 1
            arr[mx][0][1] -= 1
            arr[0][my][1] -= 1
            arr[mx][my][1] += 2
        else:
            arr[0][my][1] += 1
            arr[mx][0][1] += 1
            arr[mx][my][1] -= 2
    np_arr = np.array(arr)
    np_arr = np.cumsum(np_arr, axis=0)
    np_arr = np.cumsum(np_arr, axis=1)
    print(int(np.max(np_arr)))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
k2 = k*2
#ddprint(f"{n=} {k=} {k2=}")
a = [[0]*k2 for i in range(k2)]
for i in range(n):
    x,y,c = input().split()
    xx = int(x)%k2
    yy = (int(y)+(k if c=='B' else 0))%k2
    #ddprint(f"{x=} {y=} {c=} {xx=} {yy=}")
    a[xx][yy] += 1

#ddprint("loc1")
racc = [[0]*k2 for i in range(k2)]
rx = [[0]*k2 for i in range(k2)]
for i in range(k2):
    #if i%100==0:
    #    ddprint(i)
    for j in range(k2):
        racc[i][j] = (0 if j==0 else racc[i][j-1])+a[i][j]
    rsum = sum(a[i])
    for j in range(k):
        rx[i][j] = racc[i][j+k-1]-(0 if j==0 else racc[i][j-1])
    for j in range(k,k2):
        rx[i][j] = rsum-rx[i][j-k]

cacc = [[0]*k2 for i in range(k2)]
cx = [[0]*k2 for i in range(k2)]
for i in range(k2):
    #if i%100==0:
    #    ddprint(i)
    for j in range(k2):
        cacc[j][i] = (0 if j==0 else cacc[j-1][i])+rx[j][i]
if False and DBG:
    for i in range(k2):
        ddprint(a[i])
    ddprint('')
    for i in range(k2):
        ddprint(rx[i])
    ddprint('')
    for i in range(k2):
        ddprint(cacc[i])

mx = 0
for i in range(k2):
    #if i%100==0:
    #    ddprint(i)
    for j in range(k2):
        ii = (i+k)%k2
        if j<k:
            v1 = cacc[j+k-1][i]-(0 if j==0 else cacc[j-1][i])
            v2 = cacc[k2-1][ii] - (cacc[j+k-1][ii]- \
                   (0 if j==0 else cacc[j-1][ii]))
        else:
            jj = j-k
            v1 = cacc[k2-1][i] - (cacc[jj+k-1][i]- \
                   (0 if jj==0 else cacc[jj-1][i]))
            v2 = cacc[jj+k-1][ii]- \
                   (0 if jj==0 else cacc[jj-1][ii])
        mx = max(mx,v1+v2)
print(mx)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()


def main():
    n, k = map(int, input().split())
    K = k * 2
    """
    K * Kに点を全て移したので、この中で黒模様の左下の頂点を全探索。
    二次元累積和で各場合についてO(1)で計算可能。

    まず前準備として白マスはxかyに関してkずらすことで黒マスにできる。こうすれば記述量はもっと減らせた。
    """
    hope = [[0] * (K + 1) for _ in range(K + 1)]
    for _ in range(n):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == 'B':
            """あとで累積和を0-indexedで取る都合上、頂点座標は1-indexedにしておく。"""
            hope[1 + y % K][1 + x % K] += 1
        if c == 'W':
            hope[1 + (y + k) % K][1 + x % K] += 1

    """
    二次元累積和の書き方に悩んでたのは失態。
    やってみて気づいたが、やはり累積和は0-indexedにしないと後々の取り扱いが非常に面倒。
    """
    sumB = [[0] * (K + 1) for _ in range(K + 1)]
    for y in range(1, K + 1):
        for x in range(1, K + 1):
            sumB[y][x] = sumB[y-1][x] + sumB[y][x-1] + hope[y][x] - sumB[y-1][x-1]

    def calc_sum(x0, y0, x1, y1):
        # (x0, y0)が左下、(x1, y1)が右上となる矩形領域の値を返す
        return sumB[y1][x1] - sumB[y0-1][x1] - sumB[y1][x0-1] + sumB[y0-1][x0-1]

    """
    あとは黒四角の左下頂点(x, y)に関して全探索。
    """
    ans = 0
    for y in range(1, K+1):
        for x in range(1, k+1):
            if y <= k:
                val = (calc_sum(1, 1, x-1, y-1) + calc_sum(x, y, x+k-1, y+k-1)
                        + calc_sum(x+k, y+k, K, K) + calc_sum(x+k, 1, K, y-1)
                        + calc_sum(1, y+k, x-1, K))
                ans = max(ans, val)
            else:
                val = (calc_sum(x, 1, x+k-1, y-k-1) + calc_sum(1, y-k, x-1, y-1)
                        + calc_sum(x+k, y-k, K, y-1) + calc_sum(x, y, x+k-1, K))
                ans = max(ans, val)
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = map(int, readline().split())
    l = 2 * k
    grid = [[0] * (2 * l) for _ in range(2 * l)]

    for i in range(n):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == "W":
            x += k
        mx, my = x % l, y % l
        grid[mx][my] += 1
        grid[mx + k][my] -= 1
        grid[mx][my + k] -= 1
        grid[mx + k][my + k] += 1
        grid[mx + k][my + k] += 1
        grid[mx + 2 * k][my + k] -= 1
        grid[mx + k][my + 2 * k] -= 1
        grid[mx + 2 * k][my + 2 * k] += 1

    for x in range(1, 2 * l):
        for y in range(2 * l):
            grid[x][y] += grid[x - 1][y]

    for x in range(2 * l):
        for y in range(1, 2 * l):
            grid[x][y] += grid[x][y - 1]

    count = [[0] * l for _ in range(l)]

    for x in range(2 * l):
        for y in range(2 * l):
            count[x % l][y % l] += grid[x][y]
    ans = 0
    for x in range(l):
        for y in range(l):
            ans = max(ans, count[x][y])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
sc = iter(open(0).read().split())
ni = lambda: int(next(sc))
ns = lambda: next(sc)

N, K = ni(), ni()

K2 = K * 2
A = [[0] * K2 for _ in range(K2)]
for _ in range(N):
    x, y, c = ni(), ni(), ns()
    if c == "W":
        y += K
    A[y % K2][x % K2] += 1

S = [[0] * (K2 + 1) for _ in range(K2 + 1)]
for i in range(K2):
    for j in range(K2):
        S[i + 1][j + 1] = (
            A[i][j]
            + S[i + 1][j]
            + S[i][j + 1]
            - S[i][j]
        )

ans = 0
for i in range(K, K2 + 1):
    for j in range(K, K2 + 1):
        res = (
            S[i][j] + S[i - K][j - K] - S[i - K][j] - S[i][j - K]
            + S[i - K][j - K]
            + S[K2][j - K] - S[i][j - K]
            + S[i - K][K2] - S[i - K][j]
            + S[K2][K2] + S[i][j] - S[i][K2] - S[K2][j]
        )
        ans = max(ans, res, N - res)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def accumrate(h,w,acc,A):
  for i in range(1,h+1):
    for j in range(1,w+1):
      acc[i][j] = acc[i][j-1] + A[i-1][j-1]
  for i in range(1,h+1):
    for j in range(1,w+1):
      acc[i][j] += acc[i-1][j]
      
def cal(i,j,g,r,acc):
  return acc[g][r] + acc[i][j] - acc[g][j] - acc[i][r]

n,k = map(int,input().split())
K = 2*k
cw = [[0]*K for i in range(K)]
cb = [[0]*K for i in range(K)]
sw = 0
sb = 0
for i in range(n):
  x,y,c = input().split()
  if c == 'B':
    cb[int(x)%K][int(y)%K] += 1
    sb += 1
  else:
    cw[int(x)%K][int(y)%K] += 1
    sw += 1
    
acw = [[0]*(K+1) for i in range(K+1)]
acb = [[0]*(K+1) for i in range(K+1)]
accumrate(K,K,acb,cb)
accumrate(K,K,acw,cw)

ans = 0
for i in range(k):
  for j in range(k):
    chk_b = cal(0,0,i,j,acb)+cal(i,j,i+k,j+k,acb)+cal(i+k,j+k,K,K,acb)+cal(0,j+k,i,K,acb)+cal(i+k,0,K,j,acb)
    chk_w = cal(0,0,i,j,acw)+cal(i,j,i+k,j+k,acw)+cal(i+k,j+k,K,K,acw)+cal(0,j+k,i,K,acw)+cal(i+k,0,K,j,acw)
    ans = max(ans,max(chk_b+sw-chk_w,chk_w+sb-chk_b))
    
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
MX = 2*K
A = [[0]*MX for _ in range(MX)]
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == "W":
        y += K
    A[y%MX][x%MX] += 1
S = [[0]*(MX+1) for _ in range(MX+1)]
for y in range(MX):
    for x in range(MX):
        S[y+1][x+1] = S[y+1][x] + S[y][x+1] - S[y][x] + A[y][x]
ans = 0
for y in range(K, MX+1):
    for x in range(K, MX+1):
        s = S[y][x] - S[y-K][x] - S[y][x-K] + S[y-K][x-K]
        s += S[y-K][x-K]
        s += S[MX][x-K] - S[y][x-K]
        s += S[y-K][MX] - S[y-K][x]
        s += S[MX][MX] - S[y][MX] - S[MX][x] + S[y][x]
        ans = max(ans, s, N-s)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
xyc_=[list(input().split()) for _ in range(n)]
xyc=[]
for x,y,c in xyc_:
  x=int(x)%(2*k)
  y=int(y)%(2*k)
  if x>=k and y>=k:
    x%=k
    y%=k
  elif x>=k:
    x%=k
    c='W' if c=='B' else 'B'
  elif y>=k:
    y%=k
    c='W' if c=='B' else 'B'
  xyc.append([x,y,c])

wmap=[[0]*k for _ in range(k)]
bmap=[[0]*k for _ in range(k)]
for x,y,c in xyc:
  if c=='B':
    bmap[x][y]+=1
  else:
    wmap[x][y]+=1
for i in range(k):
  for j in range(k-1):
    bmap[i][j+1]+=bmap[i][j]
    wmap[i][j+1]+=wmap[i][j]
for i in range(k):
  for j in range(k-1):
    bmap[j+1][i]+=bmap[j][i]
    wmap[j+1][i]+=wmap[j][i]
#print(xyc)
#for b in bmap:
#  print(b)
#for w in wmap:
#  print(w)

def func(x,y):
  bret,wret=0,0
  bret=bmap[-1][-1]
  wret=wmap[-1][-1]
  if x==0 and y==0:
    pass
  elif x==0:
    bret-=bmap[-1][y-1]
    wret-=wmap[-1][y-1]
  elif y==0:
    bret-=bmap[x-1][-1]
    wret-=wmap[x-1][-1]
  else:
    bret-=bmap[-1][y-1]
    wret-=wmap[-1][y-1]
    bret-=bmap[x-1][-1]
    wret-=wmap[x-1][-1]
    bret+=2*bmap[x-1][y-1]
    wret+=2*wmap[x-1][y-1]
  return max(wmap[-1][-1]-wret+bret,bmap[-1][-1]-bret+wret)
ans=0
for i in range(k):
  for j in range(k):
    ans=max(ans,func(i,j))
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 縦K、横2*Kの長方形に全ての希望をWとして入れる
# numpyの累積和、最後にmaxをとる
N, K = lr()
table = [[0] * 2*K for _ in range(K)]
for _ in range(N):
    x, y, c = sr().split()
    x = int(x); y = int(y)
    if c == 'B':
        x -= K  # ここで全てWとして扱える
    x %= 2 * K; y %= 2 * K
    if x >= K and y >= K:
        x -= K; y -= K
    elif y >= K:
        x += K; y -= K
    # 長方形に入った
    table[y][x] += 1

table = np.array(table, dtype=np.int32)
table = np.concatenate([table, table], axis=1)
table2 = np.roll(table, K, axis=1)
table = np.concatenate([table, table2], axis=0)
table_cum = table.cumsum(axis=1).cumsum(axis=0)
prev = table_cum.copy()
table_cum[:, K:] -= prev[:, :-K]
table_cum[K:, :] -= prev[:-K, :]
table_cum[K:, K:] += prev[:-K, :-K]
answer = table_cum.max()
print(answer)

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, K = map(int, input().split())
X, Y, C = [[0] * N for _ in range(3)]

mem = [[0] * (4 * K + 1) for _ in range(4 * K + 1)]

for i in range(N):
    S = input().split()
    X[i], Y[i], C[i] = int(S[0]), int(S[1]), S[2]
    x, y = X[i] % (2 * K) + 1, (Y[i] + (K if C[i] == "W" else 0)) % (2 * K) + 1
    mem[x][y] += 1
    mem[x + K][y] -= 1
    mem[x][y + K] -= 1
    mem[x + K][y + K] += 1

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

ans = 0
for h in range(K + 1):
    for w in range(K + 1):
        s = mem[h][w] + mem[h + 2 * K][w] + mem[h][w + 2 * K] + mem[h + K][w + K] + mem[h + 2 * K][w + 2 * K]
        ans = max(ans, s)

for h in range(K + 1):
    for w in range(K, 2 * K + 1):
        s = mem[h][w] + mem[h + 2 * K][w] + mem[h + K][w - K] + mem[h + K][w + K]
        ans = max(ans, s)


print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
d = [[0 for _ in range(k+1)] for _ in range(k+1)]
e = [[0 for _ in range(k+1)] for _ in range(k+1)]
cnt_d, cnt_e = 0, 0

for _ in range(n):
    x, y, c = input().split()
    x, y = int(x), int(y)

    res = (x // k + y // k) % 2
    if (res == 0 and c == 'B') or (res == 1 and c == 'W'):
        d[x%k+1][y%k+1] += 1
        cnt_d += 1
    else:
        e[x%k+1][y%k+1] += 1
        cnt_e += 1

for i in range(k+1):
    for j in range(k):
        d[i][j+1] += d[i][j]
        e[i][j+1] += e[i][j]

for j in range(k+1):
    for i in range(k):
        d[i+1][j] += d[i][j]
        e[i+1][j] += e[i][j]


ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        res_d = d[-1][-1] - d[i-1][-1] - d[-1][j-1] + 2 * d[i-1][j-1]
        res_e = e[-1][-1] - e[i-1][-1] - e[-1][j-1] + 2 * e[i-1][j-1]
        ans = max(ans,res_d + cnt_e - res_e, res_e + cnt_d - res_d)

print(ans)