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: Wrong Answer

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()]
  xy=[[int(lst[0]) % (2*k),(int(lst[1])+k*(1^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(np.max(cand))
  
if __name__=='__main__':
  main()

Submission status: Wrong Answer

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(np.max(cand))
  
if __name__=='__main__':
  main()

Submission status: Wrong Answer

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((k+1,2*k+1),dtype='uint64')
  cand=np.zeros((k+1,k+1),dtype='uint64')
  for e in xyc:
    f0=e[0]>=k
    f1=e[1]>=k
    mat[e[0]-f0*k+1,e[1]+(-1)**f1*f0*k+1]+=e[2]
    mat[e[0]-f0*k+1,e[1]+(-1)**f1*(1^f0)*k+1]+=1-e[2]
  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(np.max(cand))
  
if __name__=='__main__':
  main()

Submission status: Wrong Answer

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((k+1,2*k+1),dtype='int64')
  cand=np.zeros((k+1,k+1),dtype='int64')
  for e in xyc:
    f0=e[0]>=k
    f1=e[1]>=k
    mat[e[0]-f0*k+1,e[1]+(-1)**f1*f0*k+1]+=e[2]
    mat[e[0]-f0*k+1,e[1]+(-1)**f1*(1^f0)*k+1]+=1-e[2]
  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(np.max(cand))
  
if __name__=='__main__':
  main()

Submission status: Wrong Answer

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((k+1,k+1),dtype='int64')
  for i in range(4):
    for x,y,c in xyc:
      mat[c,x+1+2*k*(i&1),y+1+2*k*(i>>1&1)]+=1
  mat=mat[:,:3*k+1,:3*k+1]
  for i in range(1,3*k+1):
      mat[:,:,i]+=mat[:,:,i-1]
  for i in range(1,3*k+1):
      mat[:,i,:]+=mat[:,i-1,:]
  cand=mat[0,k:2*k+1,k:2*k+1]+mat[0,:k+1,:k+1]-mat[0,k:2*k+1,:k+1]-mat[0,:k+1,k:2*k+1]
  cand+=mat[0,2*k:3*k+1,2*k:3*k+1]+mat[0,k:2*k+1,k:2*k+1]-mat[0,2*k:3*k+1,k:2*k+1]-mat[0,k:2*k+1,2*k:3*k+1]
  cand+=mat[1,2*k:3*k+1,k:2*k+1]+mat[1,k:2*k+1,:k+1]-mat[1,2*k:3*k+1,:k+1]-mat[1,k:2*k+1,k:2*k+1]
  cand+=mat[1,k:2*k+1,2*k:3*k+1]+mat[1,:k+1,k:2*k+1]-mat[1,:k+1,2*k:3*k+1]-mat[1,k:2*k+1,k:2*k+1]
  print(max(np.max(cand),np.max(mat[1,2*k,2*k]-mat[0,2*k,2*k]+cand)))
  
if __name__=='__main__':
  main()

Submission status: Wrong Answer

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.uint8)
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: Wrong Answer

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.uint8)
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: Wrong Answer

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
board = np.cumsum(board, axis=0)
board = np.cumsum(board, axis=1)
exit()
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: Wrong Answer

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
exit()
board = np.cumsum(np.cumsum(board, axis=0), axis=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: Wrong Answer

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[0, :] = 0
board[:, 0] = 0
board = np.cumsum(np.cumsum(board, axis=0), axis=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: Wrong Answer

Solution code:
import numpy as np
N, K, *XYC = open(0).read().split()
N = int(N)
K = int(K)
board = np.zeros((2 * K, 2 * K), 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
board2 = np.zeros((2 * K + 1, 2 * K + 1), dtype=np.int64)
board2[1:, 1:] = board
board = board2
cum = np.cumsum(np.cumsum(board, axis=0), axis=1)
ans = np.max(cum[K:2 * K, K:2 * K] + cum[:K, :K] - cum[:K, K:2 * K] -
             cum[K:2 * K, :K])
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, K, *XYC = open(0).read().split()
N = int(N)
K = int(K)
board = np.zeros((2 * K, 2 * K), 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
board2 = np.zeros((2 * K + 1, 2 * K + 1), dtype=np.int64)
board2[1:, 1:] = board
board = board2
cum = np.cumsum(np.cumsum(board, axis=0), axis=1)
ans = np.max(cum[K:, K:] + cum[:-K, :-K] - cum[:-K, K:] - cum[K:, :-K])
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, K, *XYC = open(0).read().split()
N = int(N)
K = int(K)
board = np.zeros((2 * K, 2 * K), 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
board2 = np.zeros((2 * K + 1, 2 * K + 1), dtype=np.int64)
board2[1:, 1:] = board
board = board2
cum = np.cumsum(np.cumsum(board, axis=0), axis=1)


def calc(cum):
    ans = np.max(cum[K:, K:] + cum[:-K, :-K] - cum[:-K, K:] - cum[K:, :-K])
    print(ans)


calc(board)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
if k==1:
  o=e=0
  for _ in range(n):
    x,y,c=input().split()
    x=int(x)
    y=int(y)
    if c=="B":y+=k
    if (x+y)%2:o+=1
    else:e+=1
  print(max(o,e))
  exit()
a=[2*k*[0]for _ in range(2*k)]
b=[(2*k+1)*[0]for _ in range(2*k+1)]
def add(i,j):
  global a
  a[min(max(0,i),2*k-1)][min(max(0,j),2*k-1)]+=1
  a[min(max(0,i+k),2*k-1)][min(max(0,j+k),2*k-1)]+=1
  a[min(max(0,i+k),2*k-1)][min(max(0,j),2*k-1)]-=1
  a[min(max(0,i),2*k-1)][min(max(0,j+k),2*k-1)]-=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
  add(x,y)
  add(x+k,y+k)
  add(x+k,y-k)
  add(x-k,y+k)
  add(x-k,y-k)
  add(x+2*k,y)
  add(x-2*k,y)
  add(x,y+2*k)
  add(x,y-2*k)
ans=0
for i in range(1,2*k+1):
  for j in range(1,2*k+1):
    b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i-1][j-1]
    ans=max(ans,b[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[2*k*[0]for _ in range(2*k)]
b=[(2*k+1)*[0]for _ in range(2*k+1)]
def add(i,j):
  global a
  a[min(max(0,i),2*k-1)][min(max(0,j),2*k-1)]+=1
  a[min(max(0,i+k),2*k-1)][min(max(0,j+k),2*k-1)]+=1
  a[min(max(0,i+k),2*k-1)][min(max(0,j),2*k-1)]-=1
  a[min(max(0,i),2*k-1)][min(max(0,j+k),2*k-1)]-=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
  add(x,y)
  add(x+k,y+k)
  add(x+k,y-k)
  add(x-k,y+k)
  add(x-k,y-k)
  add(x+2*k,y)
  add(x-2*k,y)
  add(x,y+2*k)
  add(x,y-2*k)
ans=0
for i in range(1,2*k+1):
  for j in range(1,2*k+1):
    b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i-1][j-1]
    ans=max(ans,b[i][j])
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
class CumulativeSum2D:
  def __init__(self,a):
    self.h=len(a)
    self.w=len(a[0])
    self.s=[(self.w+1)*[0]for _ in range(self.h+1)]
    for i in range(self.h):
      for j in range(self.w):
        self.s[i+1][j+1]=self.s[i+1][j]+self.s[i][j+1]-self.s[i][j]+a[i][j]
    for i in self.s:print(i)
  def sum(self,i1,j1,i2,j2):
    return self.s[i2+1][j2+1]-self.s[i1][j2+1]-self.s[i2+1][j1]+self.s[i1][j1]
n,k=map(int,input().split())
a=[4*k*[0]for _ in range(4*k)]
for _ in range(n):
  x,y,c=input().split()
  x=int(x)
  y=int(y)
  if c=="W":x+=k
  x%=2*k
  y%=2*k
  a[x][y]+=1
  a[x+k][y]-=1
  a[x][y+k]-=1
  a[x+k][y+k]+=1
  a[x+k][y+k]+=1
  a[x+k+k][y+k]-=1
  a[x+k][y+k+k]-=1
  a[x+k+k][y+k+k]+=1
b=[(4*k+1)*[0] for _ in range(4*k+1)]
ans=0
for i in range(4*k):
  for j in range(4*k):
    b[i+1][j+1]=b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]
    ans=max(ans,b[i+1][j+1])
print(ans)

Submission status: Wrong Answer

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(i,j,i+K-1,j+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: Wrong Answer

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(i,j,i+K-1,j+K-1)   
    y1,y2,x1,x2=i,i+K-1,j,i+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: Wrong Answer

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(q,p,y,x):
    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(i,j,i+K-1,j+K-1)   
    x1,x2,y1,y2=i,i+K-1,j,i+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: Wrong Answer

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(i,j,i+K-1,j+K-1)   
    x1,x2,y1,y2=i,i+K-1,j,i+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: Wrong Answer

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[x][y]+=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(i,j,i+K-1,j+K-1)   
    x1,x2,y1,y2=i,i+K-1,j,i+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: Wrong Answer

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[x][y]+=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(i,j,i+K-1,j+K-1)   
    x1,x2,y1,y2=i,i+K-1,j,i+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(a)

Submission status: Wrong Answer

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[x][y]+=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(i,j,i+K-1,j+K-1)   
    x1,x2,y1,y2=i,i+K-1,j,i+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)
print(a)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
Z=[[0]*(K*3) for i in range(K*3)]
for i in range(N):
  x,y,c=input().split()
  x,y=int(x),int(y)
  if c=='W':
    y+=K
  x%=2*K
  y%=2*K
  Z[x][y]+=1
  Z[x+K][y]-=1
  Z[x][y+K]-=1
  Z[x+K][y+K]+=1
for i in range(K):
  for j in range(K):
    Z[i][j]+=Z[i+K+K][j+K+K]
C=[[0]*(K*2+1) for i in range(K*2+1)]
for i in range(K*2):
  for j in range(K*2):
    C[i+1][j+1]=C[i+1][j]+C[i][j+1]+Z[i][j]-C[i][j]
P=0
for i in range(K+K+1):
  for j in range(K+K+1):
    P=max(P,C[i][j])
print(P)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
Z=[[0]*(K*2) for i in range(K*2)]
for i in range(N):
  x,y,c=input().split()
  x,y=int(x),int(y)
  if c=='W':
    y+=K
  x%=2*K
  y%=2*K
  Z[x][y]+=1
  x+=K
  y+=K
  x%=2*K
  y%=2*K
  Z[x][y]+=1
C=[[0]*(K*2+1) for i in range(K*2+1)]
for i in range(K*2):
  for j in range(K*2):
    C[i+1][j+1]=C[i+1][j]+C[i][j+1]+Z[i][j]-C[i][j]
P=0
for i in range(K+1):
  for j in range(K+1):
    P=max(P,C[i+K][j+K]-C[i][j+K]-C[i+K][j]+C[i][j])

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
Z=[[0]*(K*2) for i in range(K*2)]
for i in range(N):
  x,y,c=input().split()
  x,y=int(x),int(y)
  if c=='W':
    y+=K
  x%=2*K
  y%=2*K
  Z[x][y]+=1
  x+=K
  y+=K
  x%=2*K
  y%=2*K
  Z[x][y]+=1
C=[[0]*(K*2+1) for i in range(K*2+1)]
print(*Z,sep='\n')
for i in range(K*2):
  for j in range(K*2):
    C[i+1][j+1]=C[i+1][j]+C[i][j+1]+Z[i][j]-C[i][j]
P=0
for i in range(K+1):
  for j in range(K+1):
    P=max(P,C[i+K][j+K]-C[i][j+K]-C[i+K][j]+C[i][j])
print(P)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
Z=[[0]*(K*2) for i in range(K*2)]
for i in range(N):
  x,y,c=input().split()
  x,y=int(x),int(y)
  if c=='W':
    y+=K
  x%=2*K
  y%=2*K
  Z[x][y]+=1
  x+=K
  y+=K
  x%=2*K
  y%=2*K
  Z[x][y]+=1
C=[[0]*(K*2+1) for i in range(K*2+1)]
for i in range(K*2):
  for j in range(K*2):
    C[i+1][j+1]=C[i+1][j]+C[i][j+1]+Z[i][j]-C[i][j]
P=0
for i in range(K):
  for j in range(K):
    P=max(P,C[i+K][j+K]-C[i][j+K]-C[i+K][j]+C[i][j])
print(P)

Submission status: Wrong Answer

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+1):
    for y in range(1,k+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)

        ## reverse area
        sumr= 0
        if y>1:
            # top_area
            sumr += cs.query(x, max(1,y-k), min(k*2, x+k-1), y-1)
        if y-k>1:
            # bottom_area
            sumr += cs.query(x, min(k*2, y+k), min(k*2, x+k-1), min(k*2, y+k*2-1))
        if x>1:
            # left_area
            sumr += cs.query(max(1, x-k), y, x-1, min(k*2, y+k-1))
        if x>1 and y>1:
            # right_area
            sumr += cs.query(min(k*2, x+k), y, min(k*2, x+k*2-1), min(k*2, y+k-1))

        ans = max(sumd, sumr, ans)

print(ans , flush=True)

Submission status: Wrong Answer

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

def cumulative_sum_2d(collection_2d):
    result = []
    for height, column in enumerate(collection_2d):
        result.append([])
        for width, cell in enumerate(column):
            result[height].append([])
            top_sum       = result[height-1][width] if height!=0 else 0
            left_sum      = result[height][width-1] if width!=0 else 0
            duplicate_sum = result[height-1][width-1] if height!=0 and width!=0 else 0
            total_sum     = top_sum + left_sum - duplicate_sum + cell
            result[height][width] = total_sum
    for i in result:
        i.insert(0, 0)
    result.insert(0, [0 for i in result[0]])
    return result
def calc_cumulative_sum_2d(sum2d, x0, y0, x1, y1):
    return sum2d[y1][x1] - sum2d[y0-1][x1] - sum2d[y1][x0-1] + sum2d[y0-1][x0-1]

sum2d = cumulative_sum_2d(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

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 += calc_cumulative_sum_2d(sum2d, x, y, min(k*2, x+k-1), min(k*2, y+k-1))
        """
          1xk  2k
         10xxxoo
         yx000xx
         kx000xx
          x000xx
          0xxxoo
        2k0xxxoo
        """
        if x>k:
            # left_area
            sumd += calc_cumulative_sum_2d(sum2d, 1, y, x-k, min(k*2, y+k-1))
        if y>k:
            # top_area
            sumd += calc_cumulative_sum_2d(sum2d, x, 1, min(k*2, x+k-1), y-k)
        if x>1 and y>1:
            # left_top_area
            sumd += calc_cumulative_sum_2d(sum2d, 1, 1, x-1, y-1)
        if x>1 and y<k:
            # left_bottom_area
            sumd += calc_cumulative_sum_2d(sum2d, 1, y+1, x-1, k*2)
        if x<k and y>1:
            # right_top_area
            sumd += calc_cumulative_sum_2d(sum2d, x+1, 1, k*2, y-1)
        if x<k and y<k:
            # right_bottom_area
            sumd += calc_cumulative_sum_2d(sum2d, x+1, y+1, k*2, k*2)
        ans = max(sumd, ans)

print(ans , flush=True)