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: Time Limit Exceeded

Solution code:
import sys
from pprint import *
N,K=map(int,input().split())
input=sys.stdin.readline
dpw=[[0 for _ in range(2*K+1)] for _ in range(2*K+1)]
dpb=[[0 for _ in range(2*K+1)] for _ in range(2*K+1)]
def getmatnum(x1,y1,x2,y2,mat):#左上を(x1,y1)右下を(x2,y2)にしてmatの中の左上~右下の領域の和をdpから算出
    if (x2==0)or(y2==0):
        return 0
    else:
        if (x1==-1):
            x1=0
        if (y1==-1):
            y1=0
        return mat[y2][x2]-mat[y1][x2]-mat[y2][x1]+mat[y1][x1]

for i in range(N):
    x,y,c=input().split()
    x=int(x)
    y=int(y)
    #print(x,y,c)
    if c=="W":
        dpw[(y%(2*K))+1][(x%(2*K))+1]=dpw[(y%(2*K))+1][(x%(2*K))+1]+1
    else:
        dpb[(y % (2*K))+1][(x % (2*K))+1] = dpb[(y % (2*K))+1][(x % (2*K))+1] + 1
#pprint(dpw)
#pprint(dpb)

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

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

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

for i in range(1,2*K+1):
    for j in range(1,2*K+1):
        dpw[i][j]=dpw[i-1][j]+dpw[i][j]
ans=0
for i in range(K):
    for j in range(K):
        k=i+K
        l=j+K
        b1=getmatnum(-1,-1,i,j,dpb)+getmatnum(k,-1,2*K,j,dpb)+getmatnum(i,j,k,l,dpb)+getmatnum(-1,l,i,2*K,dpb)+getmatnum(k,l,2*K,2*K,dpb)
        w1=getmatnum(i,-1,k,j,dpw)+getmatnum(-1,j,i,l,dpw)+getmatnum(k,j,2*K,l,dpw)+getmatnum(i,l,k,2*K,dpw)
        b2=getmatnum(-1,-1,i,j,dpw)+getmatnum(k,-1,2*K,j,dpw)+getmatnum(i,j,k,l,dpw)+getmatnum(-1,l,i,2*K,dpw)+getmatnum(k,l,2*K,2*K,dpw)
        w2=getmatnum(i,-1,k,j,dpb)+getmatnum(-1,j,i,l,dpb)+getmatnum(k,j,2*K,l,dpb)+getmatnum(i,l,k,2*K,dpb)
        ans=max(ans,b1+w1,b2+w2)

        #print(i,j,k,l)
print(ans)
        #
#pprint(dpw)
#pprint(dpb)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
X, Y, C = [], [], []
for _ in range(n):
  x, y, c = input().split()
  X.append(int(x)%(2*k))
  Y.append(int(y)%(2*k))
  C.append(c=="B")
  G = [[0]*k for _ in range(k)]
cnt = 0
for x, y, c in zip(X, Y, C):
  if (x >= k and y < k) or (x < k and y >= k):
    x += k
    c ^= 1
  x %= k
  y %= k
  G[x][y] += (-1)**c
  cnt += c
for i in range(k):
  for j in range(k-1):
    G[i][j+1] += G[i][j]
for j in range(k):
  for i in range(k-1):
    G[i+1][j] += G[i][j]
ans = 0
for i in range(k):
  for j in range(k):
    temp = G[k-1][k-1] - G[i][k-1] - G[k-1][j] + G[i][j]*2 + cnt
    ans = max(ans, temp, n-temp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calcb(lx,ly,rx,ry):
  if rx<0 or ry<0 or lx>rx or ly>ry:
    return 0
  ret=acum1[ry][rx]
  if lx!=0:
    ret-=acum1[ry][lx-1]
  if ly!=0:
    ret-=acum1[ly-1][rx]
  if lx!=0 and ly!=0:
    ret+=acum1[ly-1][lx-1]
  return ret

def calcw(lx,ly,rx,ry):
  if rx<0 or ry<0 or lx>rx or ly>ry:
    return 0
  ret=acum2[ry][rx]
  if lx!=0:
    ret-=acum2[ry][lx-1]
  if ly!=0:
    ret-=acum2[ly-1][rx]
  if lx!=0 and ly!=0:
    ret+=acum2[ly-1][lx-1]
  return ret

n,k=map(int,input().split())
board1=[[0]*(2*k) for _ in range(2*k)]
board2=[[0]*(2*k) for _ in range(2*k)]
acum1=[[0]*(2*k) for _ in range(2*k)]
acum2=[[0]*(2*k) for _ in range(2*k)]
for _ in range(n):
  x,y,c=input().split()
  x,y=int(x)%(2*k),int(y)%(2*k)
  if c=='B':
    board1[y][x]+=1
  if c=='W':
    board2[y][x]+=1
for i in range(2*k):
  for j in range(2*k):
    acum1[i][j]=board1[i][j]
    acum2[i][j]=board2[i][j]
    if i!=0:
      acum1[i][j]+=acum1[i-1][j]
      acum2[i][j]+=acum2[i-1][j]
    if j!=0:
      acum1[i][j]+=acum1[i][j-1]
      acum2[i][j]+=acum2[i][j-1]
    if i!=0 and j!=0:
      acum1[i][j]-=acum1[i-1][j-1]
      acum2[i][j]-=acum2[i-1][j-1]
ans=0
for i in range(k):
  for j in range(k):
    tmp1=0
    tmp2=0
    lx,ly=i,j
    rx,ry=lx+k-1,ly+k-1
    #1個目のマス
    tmp1+=calcb(lx,ly,rx,ry)
    tmp2+=calcw(lx,ly,rx,ry)
    #左上のマス
    tlx,tly=0,0
    trx,ttry=lx-1,ly-1
    tmp1+=calcb(tlx,tly,trx,ttry)
    tmp2+=calcw(tlx,tly,trx,ttry)
    #右上のマス
    tlx,tly=rx+1,0
    trx,ttry=2*k-1,ly-1
    tmp1+=calcb(tlx,tly,trx,ttry)
    tmp2+=calcw(tlx,tly,trx,ttry)
    #左下のマス
    tlx,tly=0,ry+1
    trx,ttry=lx-1,2*k-1
    tmp1+=calcb(tlx,tly,trx,ttry)
    tmp2+=calcw(tlx,tly,trx,ttry)
    #右下のマス
    tlx,tly=rx+1,ry+1
    trx,ttry=2*k-1,2*k-1
    tmp1+=calcb(tlx,tly,trx,ttry)
    tmp2+=calcw(tlx,tly,trx,ttry)
    #上のマス
    tlx,tly=lx,0
    trx,ttry=rx,ly-1
    tmp1+=calcw(tlx,tly,trx,ttry)
    tmp2+=calcb(tlx,tly,trx,ttry)
    #左のマス
    tlx,tly=0,ly
    trx,ttry=lx-1,ry
    tmp1+=calcw(tlx,tly,trx,ttry)
    tmp2+=calcb(tlx,tly,trx,ttry)
    #右のマス
    tlx,tly=rx+1,ly
    trx,ttry=2*k-1,ry
    tmp1+=calcw(tlx,tly,trx,ttry)
    tmp2+=calcb(tlx,tly,trx,ttry)
    #下のマス
    tlx,tly=lx,ry+1
    trx,ttry=rx,2*k-1
    tmp1+=calcw(tlx,tly,trx,ttry)
    tmp2+=calcb(tlx,tly,trx,ttry)
    ans=max(ans,tmp1,tmp2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
 
    n, k = map(int, input().split())
 
    C = [[0]*(2*k) for _ in range(2*k)]
 
    for i in range(n):
        x, y, c = map(str, input().split())
        x, y = int(x), int(y)
        if c == 'W':
            y += k
        C[y%(2*k)][x%(2*k)] += 1
 
    #print(C)
    s = [[0]*(2*k+1) for _ in range(2*k+1)]
    for i in range(2*k):
        for j in range(2*k):
            s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + C[i][j]
 
    #print(s)
 
    def count(x1, x2, y1, y2):
        return s[y2][x2]-s[y1][x2]-s[y2][x1]+s[y1][x1]
 
    ans = 0
    for i in range(k):
        for j in range(k):
            temp = 0
            temp += count(0, j, 0, i)
            temp += count(j, j+k, i, i+k)
            temp += count(0, j, i+k, 2*k)
            temp += count(j+k, 2*k, 0, i)
            temp += count(j+k, 2*k, i+k, 2*k)
            ans = max(ans, max(temp, n-temp))
    print(ans)
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
P = [list(input().split()) for i in range(N)] # list of [x, y, c] as string
ans = 0
for x0 in range(K * 2):
    for y0 in range(K):
        count = 0
        for i in range(N):
            x = int(P[i][0])
            y = int(P[i][1])
            c = P[i][2]
            f = 1 # 希望が叶うかどうかのフラグ
            if ((x - x0) % (K * 2)) in range(K):
                if ((y - y0) % (K * 2)) in range(K):
                    if c == "W":
                        f = 0
                else:
                    if c == "B":
                        f = 0
            else:
                if ((y - y0) % (K * 2)) in range(K):
                    if c == "B":
                        f = 0
                else:
                    if c == "W":
                        f = 0
            if f == 1:
                count += 1
        if count > ans:
            ans = count
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
m = 2*k
G = [[0]*m for _ in range(m)]
for _ in range(n):
  x, y, c = input().split()
  x = int(x)%m
  y = int(y)%m
  if c == "W":
    for i in range(x+k, x+m):
      for j in range(y, y+k):
        G[i%m][j%m] += 1
    for i in range(x, x+k):
      for j in range(y+k, y+m):
        G[i%m][j%m] += 1
  else:
    for i in range(x, x+k):
      for j in range(y, y+k):
        G[i%m][j%m] += 1
    for i in range(x+k, x+m):
      for j in range(y+k, y+m):
        G[i%m][j%m] += 1
ans = max(max(g) for g in G)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n,k = list(map(int, input().split()))
v = [[0]*(2*k) for _ in range(2*k)]

for i in range(n):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    if c=="B":
        x += k
    x %= 2*k
    y %= 2*k
    v[x][y] += 1
#     v[x][y+2*k] += 1
#     v[x+2*k][y] += 1
#     v[x+2*k][y+2*k] += 1
def cumsum2(v):
    # v: h*wの2次元リスト
    h,w = len(v), len(v[0])
    v.insert(0, [0]*w)
    for l in v:
        l.insert(0, 0)
    for i in range(1,h+1):
        for j in range(1,w+1):
            v[i][j] = v[i-1][j] + v[i][j-1] - v[i-1][j-1] + v[i][j]
    return v
cumsum2(v)

def sub(c, i, j):
    i %= 2*k
    j %= 2*k
    l = []
    if i<=k and j<=k:
        l = [[i,i+k,j,j+k]]
    elif i>k and j<=k:
        l = [[i,2*k,j,j+k], [0,i-k,j,j+k]]
    elif i<=k and j>k:
        l = [[i,i+k,j,2*k], [i,i+k,0,j-k]]
    else:
        l = [[i,2*k,j,2*k], [0,i-k,j,2*k], [i,2*k,0,j-k], [0,i-k,0,j-k]]
    return sum((c[z][w] - c[z][y] - c[x][w] + c[x][y]) for x,z,y,w in l)
ans = -1
for i in range(2*k):
    for j in range(2*k):
        val0 = sub(v, i,j) + sub(v, i+k, j+k)
#         val0 = v[i+k][j+k]-v[i+k][j]-v[i][j+k]+v[i][j] + v[i+2*k][j+2*k]-v[i+2*k][j+k]-v[i+k][j+2*k]+v[i+k][j+k]
#         val1 = v[i+2*k][j+k]-v[i+2*k][j]-v[i+k][j+k]+v[i+k][j] + v[i+k][j+2*k]-v[i+k][j+k]-v[i][j+2*k]+v[i][j+k]
        ans = max(ans, val0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n,k = list(map(int, input().split()))
v = [[0]*(4*k) for _ in range(4*k)]

for i in range(n):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    if c=="B":
        x += k
    x %= 2*k
    y %= 2*k
    v[x][y] += 1
    v[x][y+2*k] += 1
    v[x+2*k][y] += 1
    v[x+2*k][y+2*k] += 1
def cumsum2(v):
    # v: h*wの2次元リスト
    h,w = len(v), len(v[0])
    v.insert(0, [0]*w)
    for l in v:
        l.insert(0, 0)
    for i in range(1,h+1):
        for j in range(1,w+1):
            v[i][j] = v[i-1][j] + v[i][j-1] - v[i-1][j-1] + v[i][j]
    return v
c = cumsum2(v)
ans = -1
for i in range(2*k):
    for j in range(2*k):
        val0 = c[i+k][j+k]-c[i+k][j]-c[i][j+k]+c[i][j] + c[i+2*k][j+2*k]-c[i+2*k][j+k]-c[i+k][j+2*k]+c[i+k][j+k]
#         val1 = c[i+2*k][j+k]-c[i+2*k][j]-c[i+k][j+k]+c[i+k][j] + c[i+k][j+2*k]-c[i+k][j+k]-c[i][j+2*k]+c[i][j+k]
        ans = max(ans, val0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import numpy as np

n,k = list(map(int, input().split()))
# v0 = np.zeros((4*k, 4*k), dtype=int)
# v1 = np.zeros((4*k, 4*k), dtype=int)
v0 = [[0]*(4*k) for _ in range(4*k)]
v1 = [[0]*(4*k) for _ in range(4*k)]

for i in range(n):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    x %= 2*k
    y %= 2*k
    if c=="W":
        v = v0
    else:
        v = v1
    v[x][y] += 1
    v[x][y+2*k] += 1
    v[x+2*k][y] += 1
    v[x+2*k][y+2*k] += 1
v0 = np.array(v0)
v1 = np.array(v1)

def cumsum2(v):
    # v: h*wの2次元リスト
    v = np.cumsum(v, axis=0)
    v = np.cumsum(v, axis=1)
    c = np.zeros((v.shape[0]+1, v.shape[1]+1), dtype=int)
    c[1:, 1:] = v
    return v
c0 = cumsum2(v0)
c1 = cumsum2(v1)
ans = -1
i0 = []
i1 = []
for i in range(2*k):
    for j in range(2*k):
        i0.append([[i+k,j+k], [i+k,j], [i,j+k], [i,j], [i+2*k, j+2*k], [i+2*k,j+k], [i+k, j+2*k], [i+k, j+k]])
        i1.append([[i+2*k, j+k], [i+2*k,j], [i+k,j+k], [i+k,j], [i+k, j+2*k], [i+k,j+k], [i,j+2*k], [i,j+k]])
#         val0 = c0[i+k][j+k]-c0[i+k][j]-c0[i][j+k]+c0[i][j] + c0[i+2*k][j+2*k]-c0[i+2*k][j+k]-c0[i+k][j+2*k]+c0[i+k][j+k]
#         val1 = c1[i+2*k][j+k]-c1[i+2*k][j]-c1[i+k][j+k]+c1[i+k][j] + c1[i+k][j+2*k]-c1[i+k][j+k]-c1[i][j+2*k]+c1[i][j+k]
#         ans = max(ans, val0+val1)
i0 = np.array(i0)
i1 = np.array(i1)
val = c0[i0[:,[0,3,4,7],0], i0[:,[0,3,4,7],1]].sum(axis=1) - c0[i0[:,[1,2,5,6],0], i0[:,[1,2,5,6],1]].sum(axis=1) + c1[i1[:,[0,3,4,7],0], i1[:,[0,3,4,7],1]].sum(axis=1) - c1[i1[:,[1,2,5,6],0], i1[:,[1,2,5,6],1]].sum(axis=1)
print(val.max())

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import numpy as np

n,k = list(map(int, input().split()))
v0 = np.zeros((4*k, 4*k), dtype=int)
v1 = np.zeros((4*k, 4*k), dtype=int)

for i in range(n):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    x %= 2*k
    y %= 2*k
    if c=="W":
        v = v0
    else:
        v = v1
    v[x][y] += 1
    v[x][y+2*k] += 1
    v[x+2*k][y] += 1
    v[x+2*k][y+2*k] += 1
def cumsum2(v):
    # v: h*wの2次元リスト
    v = np.cumsum(v, axis=0)
    v = np.cumsum(v, axis=1)
    c = np.zeros((v.shape[0]+1, v.shape[1]+1), dtype=int)
    c[1:, 1:] = v
    return v
c0 = cumsum2(v0)
c1 = cumsum2(v1)
ans = -1
i0 = []
i1 = []
for i in range(2*k):
    for j in range(2*k):
        i0.append([[i+k,j+k], [i+k,j], [i,j+k], [i,j], [i+2*k, j+2*k], [i+2*k,j+k], [i+k, j+2*k], [i+k, j+k]])
        i1.append([[i+2*k, j+k], [i+2*k,j], [i+k,j+k], [i+k,j], [i+k, j+2*k], [i+k,j+k], [i,j+2*k], [i,j+k]])
#         val0 = c0[i+k][j+k]-c0[i+k][j]-c0[i][j+k]+c0[i][j] + c0[i+2*k][j+2*k]-c0[i+2*k][j+k]-c0[i+k][j+2*k]+c0[i+k][j+k]
#         val1 = c1[i+2*k][j+k]-c1[i+2*k][j]-c1[i+k][j+k]+c1[i+k][j] + c1[i+k][j+2*k]-c1[i+k][j+k]-c1[i][j+2*k]+c1[i][j+k]
#         ans = max(ans, val0+val1)
i0 = np.array(i0)
i1 = np.array(i1)
val = c0[i0[:,[0,3,4,7],0], i0[:,[0,3,4,7],1]].sum(axis=1) - c0[i0[:,[1,2,5,6],0], i0[:,[1,2,5,6],1]].sum(axis=1) + c1[i1[:,[0,3,4,7],0], i1[:,[0,3,4,7],1]].sum(axis=1) - c1[i1[:,[1,2,5,6],0], i1[:,[1,2,5,6],1]].sum(axis=1)
print(val.max())

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import numpy as np

n,k = list(map(int, input().split()))
v0 = np.zeros((4*k, 4*k), dtype=int)
v1 = np.zeros((4*k, 4*k), dtype=int)

for i in range(n):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    x %= 2*k
    y %= 2*k
    if c=="W":
        v = v0
    else:
        v = v1
    v[x][y] += 1
    v[x][y+2*k] += 1
    v[x+2*k][y] += 1
    v[x+2*k][y+2*k] += 1
def cumsum2(v):
    # v: h*wの2次元リスト
    v = np.cumsum(v, axis=0)
    v = np.cumsum(v, axis=1)
    c = np.zeros((v.shape[0]+1, v.shape[1]+1), dtype=int)
    c[1:, 1:] = v
    return v
c0 = cumsum2(v0)
c1 = cumsum2(v1)
ans = -1
for i in range(2*k):
    for j in range(2*k):
        val0 = c0[i+k][j+k]-c0[i+k][j]-c0[i][j+k]+c0[i][j] + c0[i+2*k][j+2*k]-c0[i+2*k][j+k]-c0[i+k][j+2*k]+c0[i+k][j+k]
        val1 = c1[i+2*k][j+k]-c1[i+2*k][j]-c1[i+k][j+k]+c1[i+k][j] + c1[i+k][j+2*k]-c1[i+k][j+k]-c1[i][j+2*k]+c1[i][j+k]
        ans = max(ans, val0+val1)
print(ans)

Submission status: Time Limit Exceeded

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


def main():
    n, k = map(int, input().split())
    
    white = [[0]*(4*k+1) for _ in range(4*k+1)]
    black = [[0]*(4*k+1) for _ in range(4*k+1)]
    for i in range(n):
        x, y, z = input().split()
        if z == "B":
            black[int(x)%(2*k)+1][int(y)%(2*k)+1] += 1
            black[int(x)%(2*k)+1+2*k][int(y)%(2*k)+1] += 1
            black[int(x)%(2*k)+1][int(y)%(2*k)+1+2*k] += 1
            black[int(x)%(2*k)+1+2*k][int(y)%(2*k)+1+2*k] += 1
        else:
            white[int(x)%(2*k)+1][int(y)%(2*k)+1] += 1
            white[int(x)%(2*k)+1+2*k][int(y)%(2*k)+1] += 1
            white[int(x)%(2*k)+1][int(y)%(2*k)+1+2*k] += 1
            white[int(x)%(2*k)+1+2*k][int(y)%(2*k)+1+2*k] += 1
    
    for i in range(4*k):
        for j in range(4*k):
            white[i+1][j+1] += white[i][j+1]+white[i+1][j]-white[i][j]
            black[i+1][j+1] += black[i][j+1]+black[i+1][j]-black[i][j]
    
    
    ans = 0
    for i in range(2*k):
        for j in range(2*k):
            p, q = i+k, j+k
            x, y = i+2*k, j+2*k
            sub = white[p][q]+white[i][j]-white[p][j]-white[i][q]\
                 +white[x][y]+white[p][q]-white[x][q]-white[p][y]\
                 +black[x][q]+black[p][j]-black[p][q]-black[x][j]\
                 +black[p][y]+black[i][q]-black[i][y]-black[p][q]
            if ans < sub:
                ans = sub
    
    print(ans)

    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
v0 = [[0]*(4*k) for _ in range(4*k)]
v1 = [[0]*(4*k) for _ in range(4*k)]

for i in range(n):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    x %= 2*k
    y %= 2*k
    if c=="W":
        v = v0
    else:
        v = v1
    v[x][y] += 1
    v[x][y+2*k] += 1
    v[x+2*k][y] += 1
    v[x+2*k][y+2*k] += 1
def cumsum2(v):
    # v: h*wの2次元リスト
    h,w = len(v), len(v[0])
    v.insert(0, [0]*w)
    for l in v:
        l.insert(0, 0)
    for i in range(1,h+1):
        for j in range(1,w+1):
            v[i][j] = v[i-1][j] + v[i][j-1] - v[i-1][j-1] + v[i][j]
    return v
c0 = cumsum2(v0)
c1 = cumsum2(v1)
ans = -1
for i in range(2*k):
    for j in range(2*k):
        val0 = c0[i+k][j+k]-c0[i+k][j]-c0[i][j+k]+c0[i][j] + c0[i+2*k][j+2*k]-c0[i+2*k][j+k]-c0[i+k][j+2*k]+c0[i+k][j+k]
        val1 = c1[i+2*k][j+k]-c1[i+2*k][j]-c1[i+k][j+k]+c1[i+k][j] + c1[i+k][j+2*k]-c1[i+k][j+k]-c1[i][j+2*k]+c1[i][j+k]
        ans = max(ans, val0+val1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

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

def main():
  wb={'W':0,'B':1}
  n,k=map(int,readline().split())
  xyc=[l.split() for l in read().splitlines()]
  xyc=[[int(lst[0]) % (2*k),int(lst[1]) % (2*k),wb[lst[2]]] for lst in xyc]
  mat=np.zeros((2,4*k+1,4*k+1),dtype='int64')
  cand=np.zeros((2*k+1,2*k+1),dtype='int64')
  for i in range(4):
    for x,y,c in xyc:
      mat[c,:x+2+2*k*(i&1),:y+2+2*k*(i>>1&1)]+=1
  cand=mat[0,k:3*k+1,k:3*k+1]+mat[0,:2*k+1,:2*k+1]-mat[0,k:3*k+1,:2*k+1]-mat[0,:2*k+1,k:3*k+1]\
      +mat[0,2*k:4*k+1,2*k:4*k+1]+mat[0,k:3*k+1,k:3*k+1]-mat[0,2*k:4*k+1,k:3*k+1]-mat[0,k:3*k+1,2*k:4*k+1]\
      +mat[1,2*k:4*k+1,k:3*k+1]+mat[1,k:3*k+1,:2*k+1]-mat[1,2*k:4*k+1,:2*k+1]-mat[1,k:3*k+1,k:3*k+1]\
      +mat[1,k:3*k+1,2*k:4*k+1]+mat[1,:2*k+1,k:3*k+1]-mat[1,:2*k+1,2*k:4*k+1]-mat[1,k:3*k+1,k:3*k+1]
  print(np.max(cand))
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
square = [[0]*k*2 for _ 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
#         # center_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)

s = cs.data
for y in range(k, k*2+1):
    for x in range(k, k*2+1):
        d = cs.query(x-k+1, y-k+1, x, y)
        d += s[y-k][x-k]
        d += s[k*2][x-k] - s[y][x-k]
        d += s[y-k][k*2] - s[y-k][x]
        d += cs.query(x+1,y+1,k*2,k*2)
        ans = max(ans, d, n-d)

print(ans , flush=True)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
def main():
    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)

main()

Submission status: Time Limit Exceeded

Solution code:
n,k= map(int,input().split())
btab = [[0 for _ in range(2*k+1)] for _ in range(2*k+1)]
wtab = [[0 for _ in range(2*k+1)] for _ in range(2*k+1)]
for i in range(n):
    xs,ys,c= input().split()
    x,y=int(xs),int(ys)
    if c=='B':
        btab[y%(2*k)+1][x%(2*k)+1] += 1
    else:wtab[y%(2*k)+1][x%(2*k)+1] += 1

for i in range(1,2*k+1):
    for j in range(1,2*k+1):
        btab[i][j]+=btab[i][j-1]
        wtab[i][j]+=wtab[i][j-1]
for j in range(1,2*k+1):
    for i in range(1,2*k+1):
        btab[i][j]+=btab[i-1][j]
        wtab[i][j]+=wtab[i-1][j]
def calkim(x1,y1,x2,y2,color):
    im=0
    if x1>x2 or y1>y2:return 0
    if color=='B':im = btab[y2][x2]-btab[y1-1][x2]-btab[y2][x1-1]+btab[y1-1][x1-1]
    else:im = wtab[y2][x2]-wtab[y1-1][x2]-wtab[y2][x1-1]+wtab[y1-1][x1-1]
    return im

xytabb = [[0 for _ in range(k)] for _ in range(k)]
xytabw = [[0 for _ in range(k)] for _ in range(k)]
for i in range(k):
    for j in range(k):
        xl = [(1,i),(i+1,k+i),(k+i+1,2*k)]
        yl = [(1,j),(j+1,k+j),(k+j+1,2*k)]
        boxb = []
        boxw = []
        for yc in yl:
            for xc in xl:
                boxb.append(calkim(xc[0],yc[0],xc[1],yc[1],'B'))
                boxw.append(calkim(xc[0],yc[0],xc[1],yc[1],'W'))
        xytabw[i][j] = sum(boxw[0::2])+sum(boxb[1::2])
        xytabb[i][j] = sum(boxb[0::2])+sum(boxw[1::2])
bmax=wmax=0
for l in xytabb:
    for c in l:bmax=max(bmax,c)
for l in xytabw:
    for c in l:wmax=max(wmax,c)
print(max(bmax,wmax))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
 
hope = []
for i in range(N):
    a,b,c = input().split()
    a = int(a)
    b = int(b)
    if c == 'B':
        c = True
    else:
        c = False
    d = [a, b, c]
    hope.append(d)

import numpy as np

hope = np.array(hope)
    
for i in range(N):
    hope[i][0] %= (K*2)
    hope[i][1] %= (K*2)
    
for i in range(N):
    if hope[i][0] >= K:
        hope[i][0] -= K
        hope[i][2] = not(hope[i][2])
    
    if hope[i][1] >= K:
        hope[i][1] -= K
        hope[i][2] = not(hope[i][2])
        
import copy
 
color_map = []
map = []
 
for i in range(K):
    map.append(True)
 
for i in range(K):
    color_map.append(copy.deepcopy(map))
    
color_map = np.array(color_map)
    
def slice_x():
    temp = []
    for i in range(K):
        temp.append(not(color_map[i][0]))
    
    if K > 1:
        for i in range(K):
            for j in range(K-1):
                color_map[i][j] = color_map[i][j+1]
    
    for i in range(K):
        color_map[i][K-1] = temp[i]
        
    return
 
def slice_y():
    temp = np.copy(color_map[0])
    
    for i in range(K):
        temp[i] = not(temp[i])
    
    if K > 1:
        for i in range(K-1):
            color_map[i] = color_map[i+1]
            
    color_map[K-1] = temp
    
    return
  
sati = 0
max_sati = 0
 
for k in range(K):
    for j in range(K):
        for i in range(N):
            if color_map[hope[i][0]][hope[i][1]] == hope[i][2]:
                sati += 1
 
        if int(N/2) >= sati:
            sati = N - sati
 
        if max_sati < sati:
            max_sati = sati
        
        sati = 0
            
        slice_x()
    slice_y()
    
print(max_sati)

Submission status: Time Limit Exceeded

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

hope = []
for i in range(N):
    a,b,c = input().split()
    a = int(a)
    b = int(b)
    if c == 'B':
        c = True
    else:
        c = False
    d = [a, b, c]
    hope.append(d)
    
for i in range(N):
    hope[i][0] %= (K*2)
    hope[i][1] %= (K*2)
    
for i in range(N):
    if hope[i][0] >= K:
        hope[i][0] -= K
        hope[i][2] = not(hope[i][2])
    
    if hope[i][1] >= K:
        hope[i][1] -= K
        hope[i][2] = not(hope[i][2])
        
import copy

color_map = []
map = []

for i in range(K):
    map.append(True)

for i in range(K):
    color_map.append(copy.deepcopy(map))
    
def slice_x():
    temp = []
    for i in range(K):
        temp.append(not(color_map[i][0]))
    
    if K > 1:
        for i in range(K):
            for j in range(K-1):
                color_map[i][j] = color_map[i][j+1]
    
    for i in range(K):
        color_map[i][K-1] = temp[i]
        
    return

def slice_y():
    temp = color_map[0]
    
    for i in range(K):
        temp[i] = not(temp[i])
    
    if K > 1:
        for i in range(K-1):
            color_map[i] = color_map[i+1]
            
    color_map[K-1] = temp
    
    return
  
sati = 0
max_sati = 0

for k in range(K):
    for j in range(K):
        for i in range(N):
            if color_map[hope[i][0]][hope[i][1]] == hope[i][2]:
                sati += 1

        if int(N/2) >= sati:
            sati = N - sati

        if max_sati < sati:
            max_sati = sati
        
        sati = 0
            
        slice_x()
    slice_y()
    
print(max_sati)