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:
n,k = map(int, input().split())

ok = [ [0]*k for _ in range(k) ]
ng = [ [0]*k for _ in range(k) ]

ok_cnt = 0
ng_cnt = 0
for _ in range(n):
    x,y,c = map(str, input().split())
    x = int(x)%(k*2)
    y = int(y)%(k*2)
    if (x < k and y < k and c=='W') or (x >= k and y >= k and c=='W') or (x < k and y>= k and c =='B') or (x >= k and y < k and c =='B'):
        ok[x%k][y%k] += 1
        ok_cnt += 1
    else:
        ng[x%k][y%k] += 1
        ng_cnt += 1

ok_csums = [ [0]*(k+1) for _ in range(k+1)]
for i in range(k):
    for j in range(k):
        ok_csums[i+1][j+1] = ok_csums[i+1][j] + ok_csums[i][j+1] - ok_csums[i][j] + ok[i][j]

ng_csums = [ [0]*(k+1) for _ in range(k+1)]
for i in range(k):
    for j in range(k):
        ng_csums[i+1][j+1] = ng_csums[i+1][j] + ng_csums[i][j+1] - ng_csums[i][j] + ng[i][j]

    
ans = 0
# l u
for i in range(1,k+1):
    for j in range(1,k+1):
        ok_sum = ok_csums[i][j]
        ng_sum = ng_cnt - ng_csums[i][j]
        ans = max(ok_sum+ng_sum, ans)

# r b
for i in range(1,k+1):
    for j in range(1,k+1):
        ok_sum = ok_cnt - (ok_csums[i][k]-ok_csums[k][j]+ok_csums[i][j])
        ng_sum = (ng_csums[i][k]-ng_csums[k][j]+ng_csums[i][j])
        ans = max(ok_sum+ng_sum, ans)

# l b
for i in range(0,k):
    for j in range(1,k+1):
        ok_sum = ok_csums[k][j] - ok_csums[i][j]
        ng_sum = ng_cnt - (ng_csums[k][j] - ng_csums[i][j])
        ans = max(ok_sum+ng_sum, ans)

# r u
for i in range(1,k+1):
    for j in range(0,k):
        ok_sum = ok_csums[i][k] - ok_csums[i][j]
        ng_sum = ng_cnt - (ng_csums[i][k] - ng_csums[i][j])
        ans = max(ok_sum+ng_sum, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
# 2K * 2Kの正方形で一周するので、
# (X,Y) -> (X % 2K, Y % 2K)に言い換えることが出来る
# Wの表とBの表を別々で持つ
# それぞれの表で二次元累積和を持ち、範囲に対する得点を求められるようにする
# 黒いK * Kの正方形の左下隅を1000 * 1000通り全探索して最大値を求める

import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
white = [[0] * (2 * K + 1) for i in range(2 * K + 1)]
black = [[0] * (2 * K + 1) for i in range(2 * K + 1)]
# 白の数については、事前に合計を求めておいて、黒の領域で見つかった白の数を引くことにする
white_all = 0
for i in range(N):
  x,y,c = readline().split()
  x,y = int(x) % (2 * K),int(y) % (2 * K)
  if c == "W":
    white[x + 1][y + 1] += 1
    white_all += 1
  else:
    black[x + 1][y + 1] += 1
  
for i in range(1, len(white)):
  for j in range(1, len(white[i])):
    white[i][j] += white[i][j - 1]
    
for j in range(1, len(white)):
  for i in range(1, len(white[j])):
    white[i][j] += white[i - 1][j]

for i in range(1, len(black)):
  for j in range(1, len(black[i])):
    black[i][j] += black[i][j - 1]
    
for j in range(1, len(black)):
  for i in range(1, len(black[j])):
    black[i][j] += black[i - 1][j]


cases = ((0,0),(K,K),(-K,-K),(K,-K),(-K,K))
ans = 0
#test = {}

#for i in range(1, 7):
#  for j in range(1, 7):
#    test[(i,j)] = False
  
for i in range(1, K + 1):
  for j in range(1, K + 1):
    # 基本となる黒の正方形の左下隅・右上は以下の通り
    # (i,j),(i + K - 1, j + K - 1)
    # これに対して、
    # i,jともに +Kしたもの
    # i,jともに -Kしたもの
    # iは+K,jは-Kしたもの
    # iは-K,jは+Kしたもの
    # が考えられる範囲となる
    # なお、最小値は1,1、最大値は2 * K,2 * Kとなる
    black_cnt = 0
    white_cnt = 0
    for c in cases:
      x1 = i + c[0]
      y1 = j + c[1]
      x2 = x1 + K - 1
      y2 = y1 + K - 1
        
#      if x2 <= 0 or y2 <= 0:
#        continue
#      if x2 >= 2 * K + 1 or y2 >= 2 * K + 1:
#        continue
      x1 = max(1, x1)
      y1 = max(1, y1)
      x2 = min(2 * K, x2)
      y2 = min(2 * K, y2)
      if x1 > x2 or y1 > y2:
        continue
        
      # その領域の黒の数を数える
      black_cnt += black[x2][y2] - black[x2][y1 - 1] - black[x1 - 1][y2] + black[x1 - 1][y1 - 1]
      white_cnt += white[x2][y2] - white[x2][y1 - 1] - white[x1 - 1][y2] + white[x1 - 1][y1 - 1]
      
#      test[(x1,y1)] = True
      
    point = black_cnt + (white_all - white_cnt)
    if ans < point:
      ans = point
    
#for key,value in test.items():
#  if not value:
#    print(key)

print(ans)

Submission status: Wrong Answer

Solution code:
# 2K * 2Kの正方形で一周するので、
# (X,Y) -> (X % 2K, Y % 2K)に言い換えることが出来る
# Wの表とBの表を別々で持つ
# それぞれの表で二次元累積和を持ち、範囲に対する得点を求められるようにする
# 黒いK * Kの正方形の左下隅を1000 * 1000通り全探索して最大値を求める

import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
white = [[0] * (2 * K + 1) for i in range(2 * K + 1)]
black = [[0] * (2 * K + 1) for i in range(2 * K + 1)]
# 白の数については、事前に合計を求めておいて、黒の領域で見つかった白の数を引くことにする
white_all = 0
for i in range(N):
  x,y,c = readline().split()
  x,y = int(x) % (2 * K),int(y) % (2 * K)
  if c == "W":
    white[x + 1][y + 1] += 1
    white_all += 1
  else:
    black[x + 1][y + 1] += 1
  
for i in range(1, len(white)):
  for j in range(1, len(white[i])):
    white[i][j] += white[i][j - 1]
    
for j in range(1, len(white)):
  for i in range(1, len(white[j])):
    white[i][j] += white[i - 1][j]

for i in range(1, len(black)):
  for j in range(1, len(black[i])):
    black[i][j] += black[i][j - 1]
    
for j in range(1, len(black)):
  for i in range(1, len(black[j])):
    black[i][j] += black[i - 1][j]


cases = ((0,0),(K,K),(-K,-K),(K,-K),(-K,K))
ans = 0
for i in range(1, K + 2):
  for j in range(1, K + 2):
    # 基本となる黒の正方形の左下隅・右上は以下の通り
    # (i,j),(i + K - 1, j + K - 1)
    # これに対して、
    # i,jともに +Kしたもの
    # i,jともに -Kしたもの
    # iは+K,jは-Kしたもの
    # iは-K,jは+Kしたもの
    # が考えられる範囲となる
    # なお、最小値は1,1、最大値は2 * K,2 * Kとなる
    black_cnt = 0
    white_cnt = 0
    for c in cases:
      x1 = i + c[0]
      y1 = j + c[1]
      x2 = x1 + K - 1
      y2 = y1 + K - 1
      if x2 <= 0 or y2 <= 0:
        continue
      x1 = max(1, x1)
      y1 = max(1, y1)
      x2 = min(2 * K, x2)
      y2 = min(2 * K, y2)

      # その領域の黒の数を数える
      black_cnt += black[x2][y2] - black[x2][y1 - 1] - black[x1 - 1][y2] + black[x1 - 1][y1 - 1]
      white_cnt += white[x2][y2] - white[x2][y1 - 1] - white[x1 - 1][y2] + white[x1 - 1][y1 - 1]
    point = black_cnt + (white_all - white_cnt)
    if ans < point:
      ans = point
    
print(ans)

Submission status: Wrong Answer

Solution code:
# 2K * 2Kの正方形で一周するので、
# (X,Y) -> (X % 2K, Y % 2K)に言い換えることが出来る
# Wの表とBの表を別々で持つ
# それぞれの表で二次元累積和を持ち、範囲に対する得点を求められるようにする
# 黒いK * Kの正方形の左下隅を1000 * 1000通り全探索して最大値を求める

import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
white = [[0] * (2 * K + 1) for i in range(2 * K + 1)]
black = [[0] * (2 * K + 1) for i in range(2 * K + 1)]
# 白の数については、事前に合計を求めておいて、黒の領域で見つかった白の数を引くことにする
white_all = 0
for i in range(N):
  x,y,c = readline().split()
  x,y = int(x) % (2 * K),int(y) % (2 * K)
  if c == "W":
    white[x + 1][y + 1] += 1
    white_all += 1
  else:
    black[x + 1][y + 1] += 1
  
for i in range(1, len(white)):
  for j in range(1, len(white[i])):
    white[i][j] += white[i][j - 1]
    
for j in range(1, len(white)):
  for i in range(1, len(white[j])):
    white[i][j] += white[i - 1][j]

for i in range(1, len(black)):
  for j in range(1, len(black[i])):
    black[i][j] += black[i][j - 1]
    
for j in range(1, len(black)):
  for i in range(1, len(black[j])):
    black[i][j] += black[i - 1][j]


cases = ((0,0),(K,K),(-K,-K),(K,-K),(-K,K))
ans = 0
for i in range(1, K + 1):
  for j in range(1, K + 1):
    # 基本となる黒の正方形の左下隅・右上は以下の通り
    # (i,j),(i + K - 1, j + K - 1)
    # これに対して、
    # i,jともに +Kしたもの
    # i,jともに -Kしたもの
    # iは+K,jは-Kしたもの
    # iは-K,jは+Kしたもの
    # が考えられる範囲となる
    # なお、最小値は1,1、最大値は2 * K,2 * Kとなる
    black_cnt = 0
    white_cnt = 0
    for c in cases:
      x1 = i + c[0]
      y1 = j + c[1]
      x2 = x1 + K - 1
      y2 = y1 + K - 1
      if x2 <= 0 or y2 <= 0:
        continue
      x1 = max(1, x1)
      y1 = max(1, y1)
      x2 = min(2 * K, x2)
      y2 = min(2 * K, y2)

      # その領域の黒の数を数える
      black_cnt += black[x2][y2] - black[x2][y1 - 1] - black[x1 - 1][y2] + black[x1 - 1][y1 - 1]
      white_cnt += white[x2][y2] - white[x2][y1 - 1] - white[x1 - 1][y2] + white[x1 - 1][y1 - 1]
    point = black_cnt + (white_all - white_cnt)
    if ans < point:
      ans = point
    
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-

def solve():
    import numpy as np
    N, K = list(map(int, input().split()))
    grid = [[0 for _ in range(2*K)] for __ in range(2*K)]
    grid = np.array(grid)

    for _ in range(N):
        x, y, c = input().split()
        x, y = int(x), int(y)
        # 全部Bに変換する
        if c == "W":
            x += K
        # x,yを[0,2K)の範囲に変換する
        x, y = x%(2*K), y%(2*K)
        grid[x][y] = 1  # 希望の位置を1にする

    # 2次元累積和rを作る
    r = [[0 for _ in range(2*K+1)] for __ in range(2*K+1)]
    r[1][1] = grid[0][0]
    for x in range(1, 2*K):
        r[x+1][0] = r[x][0] + grid[x][0]
    for y in range(1, 2*K):
        r[0][y+1] = r[0][y] + grid[0][y]

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

    def calc(x1, y1, x2, y2):
        """[(x1,y1), (x2,y2)]の範囲の累積和を返す"""
        return r[x2+1][y2+1] - r[x2+1][y1] - r[x1][y2+1] + r[x1][y1]

    # 答えを探索する
    ans = 0
    for x in range(2*K):
        for y in range(2*K):
            """
            # grid[x][y]~grid[x+K-1][y+K-1]
            # grid[x+K][y+K]~[x+2*K-1][y+2*K-1]
            # の範囲を調べる
            """
            total = 0
            # grid[x][y]~grid[x+K-1][y+K-1]の範囲を計算する
            if x+K-1 >= 2*K and y+K-1 >= 2*K:
                # xとyがまたぐ場合
                x1, y1 = x, y
                x2, y2 = 2*K-1, 2*K-1
                total += calc(x1, y1, x2, y2)

                x3, y3 = 0, 0
                x4, y4 = (x+K-1)%(2*K), (y+K-1)%(2*K)
                total += calc(x3, y3, x4, y4)

                ans = max(ans, total)

            elif x+K-1 >= 2*K:
                # xのみまたぐ場合
                x1, y1 = x, y
                x2, y2 = 2*K-1, y+K-1
                total += calc(x1, y1, x2, y2)

                x3, y3 = 0, y1
                x4, y4 = (x+K-1)%(2*K), y2
                total += calc(x3, y3, x4, y4)

                ans = max(ans, total)
            elif y+K-1 >= 2*K:
                # yのみまたぐ場合
                x1, y1 = x, y
                x2, y2 = x+K-1, 2*K-1
                total += calc(x1, y1, x2, y2)

                x3, y3 = x1, 0
                x4, y4 = x2, (y+K-1)%(2*K)
                total += calc(x3, y3, x4, y4)

                ans = max(ans, total)
            else:
                # またがない場合
                x1, y1 = x, y
                x2, y2 = x+K-1, y+K-1
                total += calc(x1, y1, x2, y2)

                ans = max(ans, total)

            # grid[x+K][y+K]~[x+2*K-1][y+2*K-1]の範囲を計算する
            # ただし、gridの境界をまたぐ場合があることに注意
            x1, y1 = (x+K)%(2*K), (y+K)%(2*K)
            if x+2*K-1 >= 2*K and y+2*K-1 >= 2*K:
                # xとyがまたぐ場合
                x2, y2 = 2*K-1, 2*K-1
                total += calc(x1, y1, x2, y2)

                x3, y3 = 0, 0
                x4, y4 = (x+2*K-1)%(2*K), (y+2*K-1)%(2*K)
                total += calc(x3, y3, x4, y4)

                ans = max(ans, total)

            elif x+2*K-1 >= 2*K:
                # xのみまたぐ場合
                x2, y2 = 2*K-1, y+2*K-1
                total += calc(x1, y1, x2, y2)

                x3, y3 = 0, y1
                x4, y4 = (x+2*K-1)%(2*K), y2
                total += calc(x3, y3, x4, y4)

                ans = max(ans, total)
            elif y+2*K-1 >= 2*K:
                # yのみまたぐ場合
                x2, y2 = x+2*K-1, 2*K-1
                total += calc(x1, y1, x2, y2)

                x3, y3 = x1, 0
                x4, y4 = x2, (y+2*K-1)%(2*K)
                total += calc(x3, y3, x4, y4)

                ans = max(ans, total)
            else:
                # またがない場合
                x2, y2 = 2*K-1, 2*K-1
                total += calc(x1, y1, x2, y2)

                ans = max(ans, total)

    print(ans)



if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int, input().split())
_3K = 3 * K
_2K = 2 * K
G = np.zeros((_3K, _2K), dtype='int64') # 後から 2K * K に圧縮する
for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    # 2K * 2K の黒の希望に置き換え
    if c == 'B':
        x = x % (_2K)
        y = y % (_2K)
    else:
        x = (x + K) % (_2K)
        y = (y + K) % (_2K)
    # さらに、 2K * K の黒の希望に圧縮する
    if (y >= K) and (x >= K):
        x -= K
        y -= K
    if (y >= K) and (x < K):
        x += K
        y -= K
    # 塗り方は右下がどのマスに来るかの 2K * K 通り
    # → 最終的に 2K * K のグリッドで表すことができる
    # 各希望を満たす塗り方は K * K 通り
    # → 2K * K のグリッド内の希望を満たす K * K マスに 1 を加算すれば、
    #   全希望の加算後には各マス＝各塗り方がいくつの希望を満たすかがわかる
    # K * K マスに 1 を加算するには o(K^2) かかってしまう
    # → いもす法を使う
    # 塗り方を 3K * 2K の範囲で考えて累積和をとった後、 2K * K の範囲に圧縮する
    G[x, y] += 1
    G[x+K, y+K] += 1
    G[x+K, y] -= 1
    G[x, y+K] -= 1

# 3K * 2K の範囲の累積和をとる
G = G.cumsum(axis=1).cumsum(axis=0)
# 2K * K の範囲に圧縮
G = G[:_2K, :K] + G[K:_3K, K:_2K] + np.concatenate((G[_2K:_3K, :K], G[:K, K:_2K]), axis=0)
ans = G.max()
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    with open(0) as f:
        N, K = map(int, f.readline().split())
        xyc = [tuple(line.split()) for line in f.readlines()]
    grid = np.zeros((3*K, 3*K), dtype='int32')
    for x,y,c in xyc:
        x, y = int(x), int(y)
        if c == 'W':
            x += K
        grid[x%(2*K), y%(2*K)] += 1
        grid[x%(2*K)+K, y%(2*K)] += -1
        grid[x%(2*K), y%(2*K)+K] += -1
        grid[x%(2*K)+K, y%(2*K)+K] += 1
        if x%(2*K) >= K and y%(2*K) < K:
            grid[x%(2*K)-K, y%(2*K)+K] += 1
            grid[x%(2*K), y%(2*K)+K] += -1
            grid[x%(2*K)-K, y%(2*K)+2*K] += -1  
            grid[x%(2*K), y%(2*K)+2*K] += 1
        if x%(2*K) < K and y%(2*K) >= K:
            grid[x%(2*K)+K, y%(2*K)-K] += 1
            grid[x%(2*K)+2*K, y%(2*K)-K] += -1
            grid[x%(2*K)+K, y%(2*K)] += -1
            grid[x%(2*K)+2*K, y%(2*K)] += 1
        if x%(2*K) >= K and y%(2*K) >= K:
            grid[x%(2*K), y%(2*K)] += 1
            grid[x%(2*K)-K, y%(2*K)] += -1
            grid[x%(2*K), y%(2*K)-K] += -1
            grid[x%(2*K)-K, y%(2*K)-K] += 1

    grid = grid.cumsum(axis=1).cumsum(axis=0)
    grid_ld = grid[0:K, 0:K] + grid[2*K:3*K, 0:K] + grid[0:K, 2*K:3*K] + grid[2*K:3*K, 2*K:3*K]
    grid_rd = grid[K:2*K, 0:K] + grid[K:2*K, 2*K:3*K] 
    grid_lu = grid[0:K, K:2*K] + grid[2*K:3*K, K:2*K]
    grid_ru = grid[K:2*K, K:2*K]
    ans = max(np.amax(grid_ld), np.amax(grid_rd), np.amax(grid_lu), np.amax(grid_ru))
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import product

def main():
    with open(0) as f:
        N, K = map(int, f.readline().split())
        xyc = [tuple(line.split()) for line in f.readlines()]
    grid = np.zeros((4*K, 4*K), dtype='uint32')
    for x,y,c in xyc:
        x, y = int(x), int(y)
        if c == 'W':
            x += K
        grid[x%(2*K), y%(2*K)] += 1
        grid[x%(2*K)+K, y%(2*K)] += -1
        grid[x%(2*K), y%(2*K)+K] += -1
        grid[x%(2*K)+K, y%(2*K)+K] += 2
        grid[x%(2*K)+K, y%(2*K)+2*K] += -1
        grid[x%(2*K)+2*K, y%(2*K)+K] += -1
        grid[x%(2*K)+2*K, y%(2*K)+2*K] += 1
    del xyc
    grid = grid.cumsum(axis=1).cumsum(axis=0)
    grid = grid[0:2*K, 0:2*K] + grid[2*K:4*K, 0:2*K] + grid[0:2*K, 2*K:4*K] + grid[2*K:4*K, 2*K:4*K]
    ans = np.amax(grid)
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
def calc(lx,ly,rx,ry):
  if rx<0 or ry<0 or lx>rx or ly>ry:
    return 0
  ret=acum[ry*2*k+rx]
  if lx!=0:
    ret-=acum[ry*2*k+lx-1]
  if ly!=0:
    ret-=acum[(ly-1)*2*k+rx]
  if lx!=0 and ly!=0:
    ret+=acum[(ly-1)*2*k+lx-1]
  return ret

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

Submission status: Wrong Answer

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):
    tmp=0
    lx,ly=i,j
    rx,ry=lx+k-1,ly+k-1
    #1個目の黒マス
    tmp+=calcb(lx,ly,rx,ry)
    #左上の黒マス
    tlx,tly=0,0
    trx,ttry=lx-1,ly-1
    tmp+=calcb(tlx,tly,trx,ttry)
    #右上の黒マス
    tlx,tly=rx+1,0
    trx,ttry=2*k-1,ly-1
    tmp+=calcb(tlx,tly,trx,ttry)
    #左下の黒マス
    tlx,tly=0,ry+1
    trx,ttry=lx-1,2*k-1
    tmp+=calcb(tlx,tly,trx,ttry)
    #右下の黒マス
    tlx,tly=rx+1,ry+1
    trx,ttry=2*k-1,2*k-1
    tmp+=calcb(tlx,tly,trx,ttry)
    #上の白マス
    tlx,tly=lx,0
    trx,ttry=rx,ly-1
    tmp+=calcw(tlx,tly,trx,ttry)
    #左の白マス
    tlx,tly=0,ly
    trx,ttry=lx-1,ry
    tmp+=calcw(tlx,tly,trx,ttry)
    #右の白マス
    tlx,tly=rx+1,ly
    trx,ttry=2*k-1,ry
    tmp+=calcw(tlx,tly,trx,ttry)
    #下の白マス
    tlx,tly=lx,ry+1
    trx,ttry=rx,2*k-1
    tmp+=calcw(tlx,tly,trx,ttry)
    ans=max(ans,tmp)
    tmp=0
    #1個目の白マス
    tmp+=calcw(lx,ly,rx,ry)
    #左上の白マス
    tlx,tly=0,0
    trx,ttry=lx-1,ly-1
    tmp+=calcw(tlx,tly,trx,ttry)
    #右上の白マス
    tlx,tly=rx+1,0
    trx,ttry=2*k-1,ly-1
    tmp+=calcw(tlx,tly,trx,ttry)
    #左下の白マス
    tlx,tly=0,ry+1
    trx,ttry=lx-1,2*k-1
    tmp+=calcw(tlx,tly,trx,ttry)
    #右下の白マス
    tlx,tly=rx+1,ry+1
    trx,ttry=2*k-1,2*k-1
    tmp+=calcw(tlx,tly,trx,ttry)
    #上の黒マス
    tlx,tly=lx,0
    trx,ttry=rx,ly-1
    tmp+=calcb(tlx,tly,trx,ttry)
    #左の黒マス
    tlx,tly=0,ly
    trx,ttry=lx-1,ry
    tmp+=calcb(tlx,tly,trx,ttry)
    #右の黒マス
    tlx,tly=rx+1,ly
    trx,ttry=2*k-1,ry
    tmp+=calcb(tlx,tly,trx,ttry)
    #下の黒マス
    tlx,tly=lx,ry+1
    trx,ttry=rx,2*k-1
    tmp+=calcb(tlx,tly,trx,ttry)
print(ans)

Submission status: Wrong Answer

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):
    tmp=0
    lx,ly=i,j
    rx,ry=lx+k-1,ly+k-1
    #1個目の黒マス
    tmp+=calcb(lx,ly,rx,ry)
    #左上の黒マス
    tlx,tly=0,0
    trx,ttry=lx-1,ly-1
    tmp+=calcb(tlx,tly,trx,ttry)
    #右上の黒マス
    tlx,tly=rx+1,0
    trx,ttry=2*k-1,ly-1
    tmp+=calcb(tlx,tly,trx,ttry)
    #左下の黒マス
    tlx,tly=0,ry+1
    trx,ttry=lx-1,2*k-1
    tmp+=calcb(tlx,tly,trx,ttry)
    #右下の黒マス
    tlx,tly=rx+1,ry+1
    trx,ttry=2*k-1,2*k-1
    tmp+=calcb(tlx,tly,trx,ttry)
    #上の白マス
    tlx,tly=lx,0
    trx,ttry=rx,ly-1
    tmp+=calcw(tlx,tly,trx,ttry)
    #左の白マス
    tlx,tly=0,ly
    trx,ttry=lx-1,ry
    tmp+=calcw(tlx,tly,trx,ttry)
    #右の白マス
    tlx,tly=rx+1,ly
    trx,ttry=2*k-1,ry
    tmp+=calcw(tlx,tly,trx,ttry)
    #下の白マス
    tlx,tly=lx,ry+1
    trx,ttry=rx,2*k-1
    tmp+=calcw(tlx,tly,trx,ttry)
    ans=max(ans,tmp)
print(ans)

Submission status: Wrong Answer

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=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

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),int(y)
  if c=='B':
    board1[y%(2*k)][x%(2*k)]+=1
  if c=='W':
    board2[y%(2*k)][x%(2*k)]+=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):
    tmp=0
    lx,ly=i,j
    rx,ry=lx+k-1,ly+k-1
    #1個目の黒マス
    tmp+=calcb(lx,ly,rx,ry)
    #左上の黒マス
    tlx,tly=0,0
    trx,ttry=lx-1,ly-1
    tmp+=calcb(tlx,tly,trx,ttry)
    #右上の黒マス
    tlx,tly=rx+1,0
    trx,ttry=2*k-1,ly-1
    tmp+=calcb(tlx,tly,trx,ttry)
    #左下の黒マス
    tlx,tly=0,ry+1
    trx,ttry=lx-1,2*k-1
    tmp+=calcb(tlx,tly,trx,ttry)
    #右下の黒マス
    tlx,tly=rx+1,ry+1
    trx,ttry=2*k-1,2*k-1
    tmp+=calcb(tlx,tly,trx,ttry)
    #上の白マス
    tlx,tly=lx,0
    trx,ttry=rx,ry-1
    tmp+=calcw(tlx,tly,trx,ttry)
    #左の白マス
    tlx,tly=0,ly
    trx,ttry=lx-1,ry
    tmp+=calcw(tlx,tly,trx,ttry)
    #右の白マス
    tlx,tly=rx+1,ly
    trx,ttry=2*k-1,ry
    tmp+=calcw(tlx,tly,trx,ttry)
    #下の白マス
    tlx,tly=lx,ry+1
    trx,ttry=rx,2*k-1
    tmp+=calcw(tlx,tly,trx,ttry)
    ans=max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

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

N,K = IL()
data = SLL(N)
base = 10**6

BW_data = [[0 for i in range(2*K)] for i in range(2*K)]

for x,y,c in data:
  x,y = int(x)%(2*K),int(y)%(2*K)
  if c == "B":
    BW_data[y][x] += 1
  else:
    BW_data[y][x] += base

def ACC2(l):
  H = len(l)
  W = len(l[0])
  ret = [[0]*(W+1) for i in range(H+1)]
  for i in range(H):
    for j in range(W):
      ret[i+1][j+1] = ret[i+1][j] + ret[i][j+1] - ret[i][j] + l[i][j]
  return ret

def RANGE_SUM_in_ACC(l,h1,h2,w1,w2):
  return l[h2][w2]-l[h2][w1]-l[h1][w2]+l[h1][w1]

BW_ACC = ACC2(BW_data)

BW_res = [[0 for i in range(2*K)] for i in range(K)]

for j in range(K):
  for i in range(2*K):
    if i<K:
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,j,j+K,i,i+K)
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,0,max(0,j-1),0,max(0,i-1))
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,0,max(0,j-1),min(2*K,i+K),2*K)
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,min(2*K,j+K),2*K,0,max(0,i-1))
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,min(2*K,j+K),2*K,min(2*K,i+K),2*K)
    else:
      BW_res[j][i] = BW_ACC[-1][-1]-BW_res[j][i-K]
      
ans = 0
for j in range(K):
  for i in range(2*K):
    ans = max(ans,BW_res[j][i]%base+BW_res[j][(i+K)%(2*K)]//base)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

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

N,K = IL()
data = SLL(N)

B_data = [[0 for i in range(2*K)] for i in range(2*K)]
W_data = [[0 for i in range(2*K)] for i in range(2*K)]

for x,y,c in data:
  x,y = int(x)%(2*K),int(y)%(2*K)
  if c == "B":
    B_data[y][x] += 1
  else:
    W_data[y][x] += 1

def ACC2(l):
  H = len(l)
  W = len(l[0])
  ret = [[0]*(W+1) for i in range(H+1)]
  for i in range(H):
    for j in range(W):
      ret[i+1][j+1] = ret[i+1][j] + ret[i][j+1] - ret[i][j] + l[i][j]
  return ret

def RANGE_SUM_in_ACC(l,h1,h2,w1,w2):
  return l[h2][w2]-l[h2][w1]-l[h1][w2]+l[h1][w1]

B_ACC = ACC2(B_data)
W_ACC = ACC2(W_data)
del(B_data)
del(W_data)
B_res = [[0 for i in range(2*K)] for i in range(K)]
W_res = [[0 for i in range(2*K)] for i in range(K)]

for j in range(K):
  for i in range(2*K):
    if i<K:
      B_res[j][i] += RANGE_SUM_in_ACC(B_ACC,j,j+K,i,i+K)
      B_res[j][i] += RANGE_SUM_in_ACC(B_ACC,0,max(0,j-1),0,max(0,i-1))
      B_res[j][i] += RANGE_SUM_in_ACC(B_ACC,0,max(0,j-1),min(2*K,i+K),2*K)
      B_res[j][i] += RANGE_SUM_in_ACC(B_ACC,min(2*K,j+K),2*K,0,max(0,i-1))
      B_res[j][i] += RANGE_SUM_in_ACC(B_ACC,min(2*K,j+K),2*K,min(2*K,i+K),2*K)
      W_res[j][i] += RANGE_SUM_in_ACC(W_ACC,j,j+K,i,i+K)
      W_res[j][i] += RANGE_SUM_in_ACC(W_ACC,0,max(0,j-1),0,max(0,i-1))
      W_res[j][i] += RANGE_SUM_in_ACC(W_ACC,0,max(0,j-1),min(2*K,i+K),2*K)
      W_res[j][i] += RANGE_SUM_in_ACC(W_ACC,min(2*K,j+K),2*K,0,max(0,i-1))
      W_res[j][i] += RANGE_SUM_in_ACC(W_ACC,min(2*K,j+K),2*K,min(2*K,i+K),2*K)
    else:
      B_res[j][i] = B_ACC[-1][-1]-B_res[j][i-K]
      W_res[j][i] = W_ACC[-1][-1]-W_res[j][i-K]
      
ans = 0
for j in range(K):
  for i in range(2*K):
    ans = max(ans,B_res[j][i]+W_res[j][i])
print(ans)