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 numpy as np

def surround(matrix, fill=0):
  if not isinstance(matrix, list):
    raise
  if not all([isinstance(rows, list) for rows in matrix]):
    raise
  if not all([len(rows)==len(matrix[0]) for rows in matrix]):
    raise
  r = len(matrix)
  c = len(matrix[0])
  new_matrix = [[fill]*(c+2)] + [[fill]+rows+[fill] for rows in matrix] + [[fill]*(c+2)]
  return new_matrix

N, K = list(map(int, input().split()))
XYC = [input().split() for _ in range(N)]
X = [int(x) for x,y,c in XYC]
Y = [int(y) for x,y,c in XYC]
Z = [1 if c=='B' else 0 for x,y,c in XYC]

answer = 0

cells = [[0 for _ in range(2*K)] for _ in range(2*K)]
for x,y,c in zip(X,Y,Z):
  if c ==1:
    x = x % (2*K)
    y = y % (2*K)
  else:
    x = (x+K) % (2*K)
    y = y % (2*K)
  cells[x][y] += 1

cells = surround(cells, 0)
cells_np = np.array(cells)

row_cumsum = cells_np.cumsum(axis=1)
mat_cumsum = row_cumsum.cumsum(axis=0)

for i in range(K):
  for j in range(K):
    temp = mat_cumsum[i+K][j] - mat_cumsum[i][j] +\
    mat_cumsum[i][j+K] - mat_cumsum[i][j] +\
    mat_cumsum[2*K][j+K] - mat_cumsum[2*K][j] - mat_cumsum[i+K][j+K] + mat_cumsum[i+K][j] +\
    mat_cumsum[i+K][2*K] - mat_cumsum[i][2*K] - mat_cumsum[i+K][j+K] + mat_cumsum[i][j+K]
    answer = max(answer, temp)
  
print(answer)

Submission status: Wrong Answer

Solution code:
kl = set(range(1, 2 * 1000 + 10))
board_tmp = [0 for i in kl]
board = []
for i in kl:
    board.append(board_tmp[:])
n, k = map(int, input().split())
xy_list = []
nl = set(range(n))
kl = set(range(1, 2 * k + 1))
for i in nl:
    xi, yi, wb = input().split()
    xi = (int(xi) if wb == 'B' else int(xi) + k) % (2 * k)
    yi = int(yi) % (2 * k)
    board[xi+1][yi+1] += 1
for i in kl:
    for j in kl:
        board[i][j] += board[i][j - 1]
for j in kl:
    for i in kl:
        board[i][j] += board[i - 1][j]
ans = -1
kl = set(range(k+1))
for i in kl:
    for j in kl:
        ik = i + k
        jk = j + k
        a = board[i][j]
        b = board[ik][jk] - board[ik][j] \
            - board[i][jk] + board[i][j]
        c = board[2 * k][j] - board[ik][j]
        d = board[i][2 * k] - board[i][jk]
        e = board[2 * k][2 * k] - board[2 * k][jk] \
            - board[ik][2 * k] + board[ik][jk]
        ans = max(ans, a + b + c + d + e)
print(ans)

Submission status: Wrong Answer

Solution code:
kl = set(range(1, 2 * 1000 + 10))
board_tmp = [0 for i in kl]
board = []
for i in kl:
    board.append(board_tmp[:])
n, k = map(int, input().split())
xy_list = []
nl = set(range(n))
kl = set(range(1, 2 * k + 1))
for i in nl:
    xi, yi, wb = input().split()
    xi = (int(xi) if wb == 'B' else int(xi) + k) % (2 * k)
    yi = int(yi) % (2 * k)
    board[xi+1][yi+1] += 1
for i in kl:
    for j in kl:
        board[i][j] += board[i][j - 1]
for j in kl:
    for i in kl:
        board[i][j] += board[i - 1][j]
ans = -1
kl = set(range(k))
for i in kl:
    for j in kl:
        ik = i + k
        jk = j + k
        a = board[i][j]
        b = board[ik][jk] - board[ik][j] \
            - board[i][jk] + board[i][j]
        c = board[2 * k][j] - board[ik][j]
        d = board[i][2 * k] - board[i][jk]
        e = board[2 * k][2 * k] - board[2 * k][jk] \
            - board[ik][2 * k] + board[ik][jk]
        ans = max(ans, a + b + c + d + e)
print(ans)

Submission status: Wrong Answer

Solution code:
kl = set(range(1, 2 * 1000 + 10))
board_tmp = [0 for i in kl]
board = []
for i in kl:
    board.append(board_tmp[:])
n, k = map(int, input().split())
xy_list = []
nl = set(range(n))
kl = set(range(1, 2 * k + 1))
for i in nl:
    xi, yi, wb = input().split()
    xi = (int(xi) if wb == 'B' else int(xi) + k) % (2 * k)
    yi = int(yi) % (2 * k)
    board[xi+1][yi+1] += 1
# O(NK^2)
for i in kl:  # K*
    for j in kl:  # K*
        board[i][j] += board[i][j - 1]
for j in kl:  # K*
    for i in kl:  # K*
        board[i][j] += board[i - 1][j]
ans = -1
kl = set(range(2 * k))
for i in kl:
    for j in kl:
        ia = max(i - k, 0)
        ja = max(j - k, 0)
        ik = min(i + k, 2 * k)
        jk = min(j + k, 2 * k)
        a = board[i][j] - board[i][ja] \
            - board[ia][j] + board[ia][ja]  # 左下
        b = board[ik][jk] - board[ik][j] \
            - board[i][jk] + board[i][j]  # 中央
        c = board[2 * k][j] - board[ik][j]  # 右上
        d = board[i][2 * k] - board[i][jk]  # 左上
        e = board[2 * k][2 * k] - board[2 * k][jk] \
            - board[ik][2 * k] + board[ik][jk]  # 右上
        ans = max(ans, a + b + c + d + e)
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
xy_list = []
nl = set(range(n))
kl = set(range(1, 2 * k + 10))
board = [[0 for i in kl] for j in kl]
kl = set(range(1, 2 * k + 1))
for i in nl:
    xi, yi, wb = input().split()
    xi = (int(xi) if wb == 'B' else int(xi) + k) % (2 * k)
    yi = int(yi) % (2 * k)
    board[xi+1][yi+1] += 1
# O(NK^2)
for i in kl:  # K*
    for j in kl:  # K*
        board[i][j] += board[i][j - 1]
for j in kl:  # K*
    for i in kl:  # K*
        board[i][j] += board[i - 1][j]
ans = -1
kl = set(range(2 * k))
for i in kl:
    for j in kl:
        ia = max(i - k, 0)
        ja = max(j - k, 0)
        ik = min(i + k, 2 * k)
        jk = min(j + k, 2 * k)
        a = board[i][j] - board[i][ja] \
            - board[ia][j] + board[ia][ja]  # 左下
        b = board[ik][jk] - board[ik][j] \
            - board[i][jk] + board[i][j]  # 中央
        c = board[2 * k][j] - board[ik][j]  # 右上
        d = board[i][2 * k] - board[i][jk]  # 左上
        e = board[2 * k][2 * k] - board[2 * k][jk] \
            - board[ik][2 * k] + board[ik][jk]  # 右上
        ans = max(ans, a + b + c + d + e)
print(ans)

Submission status: Wrong Answer

Solution code:
kmax = 2 * 1000
board = [[0 for i in range(kmax + 10)] for j in range(kmax + 10)]
n, k = map(int, input().split())
xy_list = []
nl = set(range(n))
for i in nl:
    xi, yi, wb = input().split()
    xi = (int(xi) if wb == 'B' else int(xi) + k) % (2 * k)
    yi = int(yi) % (2 * k)
    board[xi+1][yi+1] += 1
kl = set(range(1, 2 * k + 1))
# O(NK^2)
for i in kl:  # K*
    for j in kl:  # K*
        board[i][j] += board[i][j - 1]
for j in kl:  # K*
    for i in kl:  # K*
        board[i][j] += board[i - 1][j]
ans = -1
kl = set(range(2 * k))
for i in kl:
    for j in kl:
        ia = max(i - k, 0)
        ja = max(j - k, 0)
        ik = min(i + k, 2 * k)
        jk = min(j + k, 2 * k)
        a = board[i][j] - board[i][ja] \
            - board[ia][j] + board[ia][ja]  # 左下
        b = board[ik][jk] - board[ik][j] \
            - board[i][jk] + board[i][j]  # 中央
        c = board[2 * k][j] - board[ik][j]  # 右上
        d = board[i][2 * k] - board[i][jk]  # 左上
        e = board[2 * k][2 * k] - board[2 * k][jk] \
            - board[ik][2 * k] + board[ik][jk]  # 右上
        ans = max(ans, a + b + c + d + e)
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
xy_list = []
nl = set(range(n))
for i in nl:
    xi, yi, wb = input().split()
    xi = (int(xi) if wb == 'B' else int(xi) + k) % (2 * k)
    yi = int(yi) % (2 * k)
    xy_list.append([xi, yi])
count_list = []
kl = set(range(2 * k))
for i in kl:
    for j in kl:
        count = 0
        kxy_min = [i, j]
        kxy_max = [i + k - 1, j + k - 1]
        for tmp in xy_list:
            if (kxy_min[0] <= tmp[0] <= kxy_max[0]) and (kxy_min[1] <= tmp[1] <= kxy_max[1]):
                count += 1
        count_list.append(count)
ans = max(count_list)
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
xy_list = []
nl = set(range(n))
for i in nl:
    xi, yi, wb = input().split()
    xy_list.append([int(xi), int(yi)] if wb == 'B' else[int(xi) + k, int(yi)])
count_list = []
for xy in xy_list:
    xy_min = xy
    xy_max = [xy[0] + 2 * k, xy[1] + 2 * k]
    count = 0
    for tmp in xy_list:
        if (xy_min[0] <= tmp[0] <= xy_max[0]) and (xy_min[1] <= tmp[1] <= xy_max[1]):
            count += 1
    count_list.append(count)
ans = max(count_list)
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
xy_list = []
nl = set(range(n))
for i in nl:
    xi, yi, wb = input().split()
    xy_list.append([int(xi), int(yi)] if wb == 'B' else[int(xi) + k, int(yi)])
count_list = []
for xy in xy_list:
    xy_min = xy
    xy_max = [xy[0] + k, xy[1] + k]
    count = 0
    for tmp in xy_list:
        if (xy_min[0] <= tmp[0] <= xy_max[0]) and (xy_min[1] <= tmp[1] <= xy_max[1]):
            count += 1
    count_list.append(count)
ans = max(count_list)
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split(" ")]
dm = [[0 for j in range(0, 2 * k)] for i in range(0, 2 * k)]
s = [[0 for j in range(0, 2 * k + 1)] for  i in range(0, 2 * k + 1)]

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

for i in range(1, 2 * k + 1):
    for j in range(1, 2 * k + 1):
        s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + dm[i - 1][j - 1]

def srect(i, j, r, l):
    global s
    return s[r][l] - s[r][j] - s[i][l] + s[i][j]

m = 0
for i in range(0, k):
    for j in range(0, k):
        aw = srect(i, j, i + k, j + k) + srect(i + k, j + k, 2 * k, 2 * k)
        raw = s[2 * k][2 * k] - aw
        if m < max(aw, raw):
            m = max(aw, raw)
print(m)

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split(" ")]
dm = [[0 for j in range(0, 2 * k)] for i in range(0, 2 * k)]
sw = [[0 for j in range(0, 2 * k + 1)] for  i in range(0, 2 * k + 1)]
sb = [[0 for j in range(0, 2 * k + 1)] for  i in range(0, 2 * k + 1)]

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

#for i in dm:
#    print(i)

for i in range(1, 2 * k + 1):
    for j in range(1, 2 * k + 1):
        sw[i][j] = sw[i][j - 1] + sw[i - 1][j] - sw[i - 1][j - 1]
        sb[i][j] = sb[i][j - 1] + sb[i - 1][j] - sb[i - 1][j - 1]
        if dm[i - 1][j - 1] == 1:
            sw[i][j] += 1
        elif dm[i - 1][j - 1] == 2:
            sb[i][j] += 1

def srect(s, i, j, w, h):
    return s[i + h][j + w] - s[i + h][j] - s[i][j + w] + s[i][j]

m = 0
for i in range(0, k):
    for j in range(0, k):
        aw = (sw[2 * k][k + j] - sw[2 * k][j]) + (sw[k + i][2 * k] - sw[i][2 * k]) - 2 * srect(sw, i, j, k, k)
        rab = (sb[2 * k][k + j] - sb[2 * k][j]) + (sb[k + i][2 * k] - sb[i][2 * k]) - 2 * srect(sb, i, j, k, k)
        ab = sb[2 * k][2 * k] - rab
        raw = sw[2 * k][2 * k] - aw
        if m < aw + ab:
            m = aw + ab
            #print(m, i, j)
        if m < raw + rab:
            m = raw + rab
            #print(m, i, j, "r", rab, raw, aw)
            #print(sb[2 * k][k + j], sb[2 * k][j], sb[k + i][2 * k] ,sb[i][2 * k],sb[i + k][j + k],sb[i][j])
            #print(sw[2 * k][k + j], sw[2 * k][j], sw[k + i][2 * k] ,sw[i][2 * k],sw[i + k][j + k],sw[i][j])
print(m)

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split(" ")]
dm = [[0 for j in range(0, 2 * k)] for i in range(0, 2 * k)]
sw = [[0 for j in range(0, 2 * k + 1)] for  i in range(0, 2 * k + 1)]
sb = [[0 for j in range(0, 2 * k + 1)] for  i in range(0, 2 * k + 1)]

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

#for i in dm:
#    print(i)

for i in range(1, 2 * k + 1):
    for j in range(1, 2 * k + 1):
        sw[i][j] = sw[i][j - 1] + sw[i - 1][j] - sw[i - 1][j - 1]
        sb[i][j] = sb[i][j - 1] + sb[i - 1][j] - sb[i - 1][j - 1]
        if dm[i - 1][j - 1] == 1:
            sw[i][j] += 1
        elif dm[i - 1][j - 1] == 2:
            sb[i][j] += 1

def srect(s, i, j, w, h):
    return s[i + h][j + w] - s[i + h][j] - s[i][j + w] + s[i][j]

m = 0
for i in range(0, k):
    for j in range(0, k):
        aw = (sw[2 * k][k + j] - sw[2 * k][j]) + (sw[k + i][2 * k] - sw[i][2 * k]) - 2 * srect(sw, i, j, k, k)
        rab = (sb[2 * k][k + j] - sb[2 * k][j]) + (sb[k + i][2 * k] - sb[i][2 * k]) - 2 * srect(sb, i, j, k, k)
        ab = sb[2 * k][2 * k] - rab
        raw = sw[2 * k][2 * k] - aw
        if m < aw + ab:
            m = aw + ab
            #print(m, i, j)
        if m < raw + rab:
            m = raw + rab
            print(sb[2 * k][k + j], sb[2 * k][j], sb[k + i][2 * k] ,sb[i][2 * k],sb[i + k][j + k],sb[i][j])
            print(sw[2 * k][k + j], sw[2 * k][j], sw[k + i][2 * k] ,sw[i][2 * k],sw[i + k][j + k],sw[i][j])
print(m)

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split(" ")]
dm = [["" for j in range(0, 2 * k)] for i in range(0, 2 * k)]
sw = [[0 for j in range(0, 2 * k + 1)] for  i in range(0, 2 * k + 1)]
sb = [[0 for j in range(0, 2 * k + 1)] for  i in range(0, 2 * k + 1)]

for i in range(0, n):
    x, y, c = input().split(" ")
    x = int(x) % (2 * k)
    y = int(y) % (2 * k)
    dm[x][y] = c

#for i in dm:
#    print(i)

for i in range(1, 2 * k + 1):
    for j in range(1, 2 * k + 1):
        sw[i][j] = sw[i][j - 1] + sw[i - 1][j] - sw[i - 1][j - 1]
        sb[i][j] = sb[i][j - 1] + sb[i - 1][j] - sb[i - 1][j - 1]
        if dm[i - 1][j - 1] == "W":
            sw[i][j] += 1
        elif dm[i - 1][j - 1] == "B":
            sb[i][j] += 1

m = 0
for i in range(0, k + 1):
    for j in range(0, k + 1):
        aw = (sw[2 * k][k + j] - sw[2 * k][j]) + (sw[k + i][2 * k] - sw[i][2 * k]) - (sw[i + k][j + k] - sw[i][j])
        ab = sb[2 * k][2 * k] - ((sb[2 * k][k + j] - sb[2 * k][j]) + (sb[k + i][2 * k] - sb[i][2 * k]) - (sb[i + k][j + k] - sb[i][j]))
        if m < aw + ab:
            m = aw + ab
print(m)

Submission status: Wrong Answer

Solution code:
N, K = list(map(int, input().split()))
xyc = [input().split() for _ in range(N)]

D = [[0] * (3 * K) for _ in range(3 * K)]
for i in xyc:
  x = int(i[0]) % (2 * K)
  y = int(i[1]) % (2 * K)
  if i[2] == "W":
    x = (x + K) % (2 * K)
  D[x][y] += 1
  tx = x + K
  ty = y + K
  D[tx][y] -= 1
  D[x][ty] -= 1
  D[tx][ty] += 1

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

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

Ans = 0
for i in range(2 * K):
  for j in range(2 * K):
    Ans = max(Ans, D[i][j] + D[i + K][j + K])

print(Ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())

b_map = [[0]*(2*k) for i in range(2*k)]
w_map = [[0]*(2*k) for i in range(2*k)]
max_bcnt = 0
for i in range(n):
  x,y,color = input().split()
  x = int(x)
  y = int(y)
  if color == "B":
    b_map[x%(2*k)][y%(2*k)] += 1
    max_bcnt += 1
  else:
    w_map[x%(2*k)][y%(2*k)] += 1

b_ruiseki = [[0]*(2*k+1) for i in range(2*k+1)]
w_ruiseki = [[0]*(2*k+1) for i in range(2*k+1)]
for i in range(1,2*k+1):
  for j in range(1,2*k+1):  
    b_ruiseki[i][j] = b_map[i-1][j-1] + b_ruiseki[i-1][j]  
    w_ruiseki[i][j] = w_map[i-1][j-1] + w_ruiseki[i-1][j]  
for i in range(1,2*k+1):
  for j in range(1,2*k+1):  
    b_ruiseki[i][j] = b_ruiseki[i][j]   + b_ruiseki[i][j-1]  
    w_ruiseki[i][j] = w_ruiseki[i][j]   + w_ruiseki[i][j-1] 

def w_count(x,y,ruiseki):
  ans = ruiseki[x][y]
  ans += ruiseki[x+k][y+k] - ruiseki[x+k][y] - ruiseki[x][y+k] + ruiseki[x][y] 
  ans += ruiseki[2*k][y] - ruiseki[x+k][y]
  ans += ruiseki[x][2*k] - ruiseki[x][k+y]
  ans += ruiseki[2*k][2*k] - ruiseki[2*k][y+k] - ruiseki[x+k][2*k] + ruiseki[x+k][y+k]
  return ans
res = 0
for i in range(k):
  for j in range(k):
    res = max(w_count(i,j,w_ruiseki)+ max_bcnt - w_count(i,j,b_ruiseki),res)
print(res)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())

b_map = [[0]*(2*k) for i in range(2*k)]
w_map = [[0]*(2*k) for i in range(2*k)]
max_bcnt = 0
for i in range(n):
  x,y,color = input().split()
  x = int(x)
  y = int(y)
  if color == "B":
    b_map[x%(2*k)][y%(2*k)] += 1
    max_bcnt += 1
  else:
    w_map[x%(2*k)][y%(2*k)] += 1

b_ruiseki = [[0]*(2*k+1) for i in range(2*k+1)]
w_ruiseki = [[0]*(2*k+1) for i in range(2*k+1)]
for i in range(1,2*k+1):
  for j in range(1,2*k+1):  
    b_ruiseki[i][j] = b_map[i-1][j-1] + b_ruiseki[i-1][j]  
    w_ruiseki[i][j] = w_map[i-1][j-1] + w_ruiseki[i-1][j]  
for i in range(1,2*k+1):
  for j in range(1,2*k+1):  
    b_ruiseki[i][j] = b_ruiseki[i][j]   + b_ruiseki[i][j-1]  
    w_ruiseki[i][j] = w_ruiseki[i][j]   + w_ruiseki[i][j-1] 


def w_count(x,y,ruiseki):
  ans = ruiseki[x][y]
  ans += ruiseki[x+k][y+k] - ruiseki[x+k][y] - ruiseki[x][y+k] + ruiseki[x][y] 
  ans += ruiseki[2*k][y] - ruiseki[x+k][y]
  ans += ruiseki[x][2*k] - ruiseki[x][k+y]
  ans += ruiseki[2*k][2*k] - ruiseki[2*k][y+k] - ruiseki[x+k][2*k] + ruiseki[x+k][y+k]
  return ans
res = 0
for i in range(k+1):
  for j in range(k+1):
    res = max(w_count(i,j,w_ruiseki)+ max_bcnt - w_count(i,j,b_ruiseki),res)
print(res)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
K2 = K * 2
g = [[' ' for x in range(K2)] for y in range(K2)]
for i in range(N):
    x,y,c = input().split()
    x = int(x) % (K2)
    y = int(y) % (K2)
    g[y][x] = c
cwx = []
cbx = []
for y in range(K2):
    dw=[0]
    db=[0]
    for x in range(K2):
        dw.append(dw[x] + (1 if g[y][x]=='W' else 0))
        db.append(db[x] + (1 if g[y][x]=='B' else 0))
    cwx.append(dw)
    cbx.append(db)

ans=0
for by in range(K2):
    for bx in range(K2):
        ans1=0
        # W: (x,y)-(x+K-1,y+K-1), (x+K,y+K)-(x+K2-1,y+K2-1)
        # B: (x,y+K)-(x+K-1,y+K2-1), (x+K,y)-(x+K2-1,y+K-1)
        for y in range(K2):
            if (by + y) % K2 < K:
                a = (x) % K2
                b = (x + K - 1) % K2
                if a < b:
                    ans1 += cbx[y][b + 1] - cbx[y][a]
                else:
                    ans1 += cbx[y][K2] - cbx[y][a] + cbx[y][b + 1]
                a = (x + K) % K2
                b = (x + K2 - 1) % K2
                if a < b:
                    ans1 += cwx[y][b + 1] - cwx[y][a]
                else:
                    ans1 += cwx[y][K2] - cwx[y][a] + cwx[y][b + 1]
            else:
                a = (x) % K2
                b = (x + K - 1) % K2
                if a < b:
                    ans1 += cwx[y][b + 1] - cwx[y][a]
                else:
                    ans1 += cwx[y][K2] - cwx[y][a] + cwx[y][b + 1]
                a = (x + K) % K2
                b = (x + K2 - 1) % K2
                if a < b:
                    ans1 += cbx[y][b + 1] - cbx[y][a]
                else:
                    ans1 += cbx[y][K2] - cbx[y][a] + cbx[y][b + 1]
        ans=max(ans,ans1)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int, input().split())
Si = [input().split() for _ in range(N)]

K2 = K * 2
K4 = K * 4

Gij = []
for s in Si:
    i = int(s[0]) % K2
    j = int(s[1]) % K2
    if s[2] == "B":
        i = (i + K) % K2
    Gij.append([i, j])

Mij = np.zeros((K4, K4), dtype=int)

def imos(i, j):
    if 0 <= i < K*3 and 0 <= j < K*3:
        Mij[i][j] += 1
        Mij[i + K][j] -= 1
        Mij[i][j + K] -= 1
        Mij[i + K][j + K] += 1

for i, j in Gij:
    #
    imos(i, j)
    imos(i + K, j + K)
    imos(i - K, j - K)
    imos(i - K, j + K)
    imos(i + K, j - K)

# 累積和
for i in range(K2):
    Mij[i + 1, :] += Mij[i, :]
for j in range(K2):
    Mij[:, j + 1] += Mij[:, j]


print(Mij.max())

Submission status: Wrong Answer

Solution code:
def solve(K, X_Y_C):
    # 白の左上が来る座標を(x, y)として全塗りつぶしパターンで探索
    max_achieved_count = 0
    for x in range(K):
        for y in range(2 * K):
            achieved_count = get_achieved_count(K, X_Y_C, x, y)
            if achieved_count > max_achieved_count:
                max_achieved_count = achieved_count
    return max_achieved_count


def get_achieved_count(K, X_Y_C, x, y):
    achieved_count = 0
    for x_y_c in X_Y_C:
        adj_x = int(x_y_c[0]) % (2 * K)
        adj_y = int(x_y_c[1]) % (2 * K)
        c = x_y_c[2]

        dist_x = abs(adj_x - x)
        dist_y = abs(adj_y - y)

        is_white = ((dist_x // K) + (dist_y // K)) % 2 == 0
        if (is_white and c == "W") or (not is_white and c == "B"):
            achieved_count += 1
    return achieved_count


N, K = map(int, input().split())
X_Y_C = [list(input().split()) for _ in range(N)]

print(solve(K, X_Y_C))

Submission status: Wrong Answer

Solution code:
class BIT2D:
    '''2 dimensional 1-indexed BIT
    '''

    def __init__(self, size: int):
        self.__size = size
        self.__data = [[0] * (size+1) for _ in range(size+1)]

    def update(self, x: int, y: int, v: int):
        tx, ty = x, y
        while tx <= self.__size:
            ty = y
            while ty <= self.__size:
                self.__data[tx][ty] += v
                ty += ty & -ty
            tx += tx & -tx

    def sum(self, x1: int, y1: int, x2: int, y2: int)->int:
        return self.__sum(x2, y2) - self.__sum(x2, y1) - self.__sum(x1, y2) + self.__sum(x1, y1)

    def __sum(self, x: int, y: int)->int:
        s, tx, ty = 0, x, y
        while tx > 0:
            ty = y
            while ty > 0:
                s += self.__data[tx][ty]
                ty -= ty & -ty
            tx -= tx & -tx
        return s


def points(cx: int, cy: int, K: int)->list:
    # 中心
    ps = [(max(0, cx-K), max(0, cy-K), cx, cy)]

    # 右上
    x2, y2 = min(2*K, cx+K), min(2*K, cy+K)
    x1, y1 = cx, cy
    ps.append((x1, y1, x2, y2))

    if K < cy:
        # 右下
        x2, y2 = min(2*K, cx+K), cy - K
        x1, y1 = cx, max(0, y2-K)
        ps.append((x1, y1, x2, y2))

    if cx < K:
        # 右
        x2, y2 = min(2*K, cx+2*K), cy
        x1, y1 = cx + K, max(0, cy-K)
        ps.append((x1, y1, x2, y2))

    if K < cx:
        # 左上
        x2, y2 = cx - K, min(2*K, cy+K)
        x1, y1 = max(0, x2-K), cy
        ps.append((x1, y1, x2, y2))

    if K < cx and K < cy:
        # 左下
        x2, y2 = cx - K, cy - K
        x1, y1 = max(0, x2-K), max(0, y2-K)
        ps.append((x1, y1, x2, y2))

    return ps


def checker(N: int, K: int, XYC: list)->int:
    white, black = BIT2D(2*K), BIT2D(2*K)
    for x, y, c in XYC:
        if c == 'B':
            x = x + K
        tx, ty = (x % (2*K)) + 1, (y % (2*K)) + 1
        # black.update(tx, ty, 1)
        # if c == 'W':
        white.update(tx, ty, 1)

    # white = [[0] * (2*K + 1) for _ in range(2*K + 1)]
    # black = [[0] * (2*K + 1) for _ in range(2*K + 1)]
    # # sorted(sorted(XYC, key=lambda x: x[0]), key=lambda x: x[1]):
    # for x, y, c in XYC:
    #     tx, ty = (x % (2*K)) + 1, (y % (2*K)) + 1
    #     if c == 'W':
    #         white[tx][ty] += 1
    #     if c == 'B':
    #         black[tx][ty] += 1

    # for ky in range(2*K):
    #     for kx in range(2*K):
    #         white[ky+1][kx+1] = white[ky+1][kx] + white[ky][kx+1]
    #         black[ky+1][kx+1] = black[ky+1][kx] + black[ky][kx+1]

    # print('finished initialized')

    max_count = 0
    op = 0
    for ky in range(K, 2*K):
        for kx in range(2*K):
            count = 0
            # print('-'*30)
            for x1, y1, x2, y2 in points(kx, ky, K):
                count += white.sum(x1, y1, x2, y2)
                # count += white[x2][y2] - white[x2][y1] - \
                #     white[x1][y2] + white[x1][y1]
                op += 1
                # print('white ({}, {}, {}, {})'.format(x1, y1, x2, y2))
                # print(count)

            # for x1, y1, x2, y2 in points((kx+K) % (2*K), ky, K):
            #     count += black.sum(x1, y1, x2, y2)
            #     # count += black[x2][y2] - black[x2][y1] - \
            #     #     black[x1][y2] + black[x1][y1]
            #     op += 1
            #     # print('black ({}, {}, {}, {})'.format(x1, y1, x2, y2))
            #     # print(count)

            max_count = max(max_count, count)
            if max_count == N:
                break
    print(op)
    return max_count


if __name__ == "__main__":
    N = 0
    N, K = map(int, input().split())
    XYC = []
    for _ in range(N):
        x, y, c = input().split()
        XYC.append((int(x), int(y), c))
    ans = checker(N, K, XYC)
    print(ans)

Submission status: Wrong Answer

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

N,K=rl()

W = [[0 for _ in range(2*K+3)] for _ in range(2*K+3)]
for i in range(N):
    x,y,c=input().split()
    x = int(x)%(2*K)
    y = (int(y) if c=='W' else int(y)+K)%(2*K)
    if (x<K)^(y<K):
        x %= K
        y %= K
        W[0][y+1] += 1
        W[0][y+K+1] -= 1
        W[x+1][0] += 1
        W[x+1][y+1] -= 2
        W[x+1][y+K+1] += 2
        W[x+1][2*K] -= 1
        W[x+K+1][0] -= 1
        W[x+K+1][y+1] += 2
        W[x+K+1][y+K+1] -= 2
        W[x+K+1][2*K] += 1
        W[2*K][y+1] -= 1
        W[2*K][y+K+1] += 1
    else:
        x %= K
        y %= K
        W[0][0] += 1
        W[x+1][0] -= 1
        W[0][y+1] -= 1
        W[x+1][y+1] += 2
        W[x+K+1][y+1] -= 2
        W[x+1][y+K+1] -= 2
        W[x+K+1][y+K+1] += 1
        W[x+K+1][0] += 1
        W[2*K][0] -= 1
        W[2*K][y+1] += 1
        W[0][y+K+1] += 1
        W[0][2*K] -= 1
        W[x+1][2*K] += 1

for x in range(0,2*K+1):
    for y in range(0,2*K+1):
        W[x][y] += W[x][y-1]
for y in range(0,2*K+1):
    for x in range(0,2*K+1):
        W[x][y] += W[x-1][y]

ans = 0
for x in range(K+1):
    for y in range(K+1):
        ans = max(ans,W[x][y])

print(ans)

Submission status: Wrong Answer

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

N,K=rl()

W = [[0 for _ in range(2*K+10)] for _ in range(2*K+10)]
for i in range(N):
    x,y,c=input().split()
    x = int(x)%(2*K)
    y = (int(y) if c=='W' else int(y)+K)%(2*K)
    if (x<K)^(y<K):
        x %= K
        y %= K
        W[0][y+1] += 1
        W[x+1][y+1] -= 2
        W[0][K] -= 1
        W[x+1][K] += 1
        W[x+1][0] += 1
        W[K][0] -= 1
        W[K][y+1] += 1
    else:
        x %= K
        y %= K
        W[0][0] += 1
        W[x+1][0] -= 1
        W[0][y+1] -= 1
        W[x+1][y+1] += 2
        W[K][y+1] -= 1
        W[x+1][K] -= 1
        W[K][K] += 1

for x in range(0,K+2):
    for y in range(1,K+2):
        W[x][y] += W[x][y-1]
for y in range(0,K+2):
    for x in range(1,K+2):
        W[x][y] += W[x-1][y]

ans = 0
for x in range(K+2):
    for y in range(K+2):
        ans = max(ans,W[x][y])

print(ans)

Submission status: Wrong Answer

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

N,K=rl()

W = [[0 for _ in range(2*K+3)] for _ in range(2*K+3)]
for i in range(N):
    x,y,c=input().split()
    x = int(x)%(2*K)
    y = (int(y) if c=='W' else int(y)+K)%(2*K)
    if (x<K)^(y<K):
        x %= K
        y %= K
        W[0][y+1] += 1
        W[x+1][y+1] -= 2
        W[0][K+1] -= 1
        W[x+1][K+1] += 1
        W[x+1][0] += 1
        W[K+1][0] -= 1
        W[K+1][y+1] += 1
    else:
        x %= K
        y %= K
        W[0][0] += 1
        W[x+1][0] -= 1
        W[0][y+1] -= 1
        W[x+1][y+1] += 2
        W[K+1][y+1] -= 1
        W[x+1][K+1] -= 1
        W[K+1][K+1] += 1

for x in range(0,K+2):
    for y in range(1,K+2):
        W[x][y] += W[x][y-1]
for y in range(0,K+2):
    for x in range(1,K+2):
        W[x][y] += W[x-1][y]

ans = 0
for x in range(K+2):
    for y in range(K+2):
        ans = max(ans,W[x][y])

print(ans)

Submission status: Wrong Answer

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

N,K=rl()

W = [[0 for _ in range(2*K+10)] for _ in range(2*K+10)]
for i in range(N):
    x,y,c=input().split()
    x = int(x)%(2*K)
    y = (int(y) if c=='W' else int(y)+K)%(2*K)
    if (x<K) and (y<K):
        x %= K
        y %= K
        W[0][y+1] += 1
        W[x+1][y+1] -= 2
        W[0][K+1] -= 1
        W[x+1][K+1] += 1
        W[x+1][0] += 1
        W[K+1][0] -= 1
        W[K+1][y+1] += 1
    else:
        x %= K
        y %= K
        W[0][0] += 1
        W[x+1][0] -= 1
        W[0][y+1] -= 1
        W[x+1][y+1] += 2
        W[K+1][y+1] -= 1
        W[x+1][K+1] -= 1
        W[K+1][K+1] += 1

for x in range(0,K+2):
    for y in range(1,K+2):
        W[x][y] += W[x][y-1]
for y in range(0,K+2):
    for x in range(1,K+2):
        W[x][y] += W[x-1][y]

ans = 0
for x in range(K+2):
    for y in range(K+2):
        ans = max(ans,W[x][y])

print(ans)

Submission status: Wrong Answer

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

N,K=rl()

W = [[0 for _ in range(2*K+3)] for _ in range(2*K+3)]
for i in range(N):
    x,y,c=input().split()
    x = int(x)%(2*K)
    y = (int(y) if c=='W' else int(y)+K)%(2*K)
    if (x<K)^(y<K):
        x %= K
        y %= K
        W[0][y+1] += 1
        W[x+1][y+1] -= 2
        W[0][K+1] -= 1
        W[x+1][K+1] += 1
        W[x+1][0] += 1
        W[K+1][0] -= 1
        W[K+1][y+1] += 1
    else:
        x %= K
        y %= K
        W[0][0] += 1
        W[x+1][0] -= 1
        W[0][y+1] -= 1
        W[x+1][y+1] += 2
        W[K+1][y+1] -= 1
        W[x+1][K+1] -= 1
        W[K+1][K+1] += 1

for x in range(0,K+2):
    for y in range(1,K+2):
        W[x][y] += W[x][y-1]
for y in range(0,K+2):
    for x in range(1,K+2):
        W[x][y] += W[x-1][y]

ans = 0
for x in range(K+1):
    for y in range(K+1):
        ans = max(ans,W[x][y])

print(ans)