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:
# time complexity: O(N + K^2)
# space complexity: O(K^2)

import sys
fin = sys.stdin.readline
from collections import defaultdict
from pprint import pprint

def sum_range_2D(cuml_mat, coord_left_up, Kx, Ky):
    if Kx <= 0 or Ky <= 0:
        return 0
    x, y = coord_left_up
    if x - 1 >= 0 and y - 1 >= 0:
        left_up = cuml_mat[x - 1][y - 1]
    else:
        left_up = 0
    if x - 1 >= 0 and y + Ky - 1 >= 0:
        right_up = cuml_mat[x - 1][y + Ky - 1]
    else:
        right_up = 0
    if x + Kx - 1 >= 0 and y - 1 >= 0:
        left_down = cuml_mat[x + Kx - 1][y - 1]
    else:
        left_down = 0
    right_down = cuml_mat[min(len(cuml_mat) - 1, x + Kx - 1)][min(len(cuml_mat) - 1, y + Ky - 1)]
    return right_down - right_up - left_down + left_up


N, K = [int(elem) for elem in fin().split()]
black_desires = []
for _ in range(N):
    x, y, c = fin().split()
    x = int(x) % (2 * K)
    y = int(y) % (2 * K) if c == 'B' else (int(y) + K) % (2 * K)
    black_desires.append((x, y))

cuml_2D = [[0] * (2*K) for _ in range(2*K)]
for x, y in black_desires:
    cuml_2D[x][y] += 1
for i in range(2 * K):
    for j in range(1, 2 * K):
        cuml_2D[i][j] += cuml_2D[i][j - 1]
for j in range(2 * K):
    for i in range(1, 2 * K):
        cuml_2D[i][j] += cuml_2D[i - 1][j]

max_num = 0
for i in range(K):
    for j in range(K):
        current_num = sum_range_2D(cuml_2D, (i, j), K, K) \
                    + sum_range_2D(cuml_2D, (0, 0), i, j) \
                    + sum_range_2D(cuml_2D, (0, j + K), i, K - j) \
                    + sum_range_2D(cuml_2D, (i + K, 0), K - i, j) \
                    + sum_range_2D(cuml_2D, (i + K, j + K), K - i, K - j)
        max_num = max(max_num, current_num)

for i in range(K):
    for j in range(K, 2 * K):
        current_sum = sum_range_2D(cuml_2D, (i, j), K, 2 * K - j) \
                    + sum_range_2D(cuml_2D, (0, j - K), i, K) \
                    + sum_range_2D(cuml_2D, (i + K, j - K), K - i, K) \
                    + sum_range_2D(cuml_2D, (i, 0), K, j - K)
        max_num = max(max_num, current_num)
print(max_num)

Submission status: Wrong Answer

Solution code:
# time complexity: O(N + K^2)
# space complexity: O(K^2)

import sys
fin = sys.stdin.readline
from collections import defaultdict


def sum_range_2D(cuml_mat, coord_left_up, Kx, Ky):
    if Kx <= 0 or Ky <= 0:
        return 0
    x, y = coord_left_up
    if x - 1 >= 0 and y - 1 >= 0:
        left_up = cuml_mat[x - 1][y - 1]
    else:
        left_up = 0
    if x - 1 >= 0 and y + Ky - 1 >= 0:
        right_up = cuml_mat[x - 1][y + Ky - 1]
    else:
        right_up = 0
    if x + Kx - 1 >= 0 and y - 1 >= 0:
        left_down = cuml_mat[x + Kx - 1][y - 1]
    else:
        left_down = 0
    right_down = cuml_mat[min(2 * Kx - 1, x + Kx - 1)][min(2 * Ky - 1, y + Ky - 1)]
    return right_down - right_up - left_down + left_up


N, K = [int(elem) for elem in fin().split()]
black_desires = []
for _ in range(N):
    x, y, c = fin().split()
    x = int(x) % (2 * K)
    y = int(y) % (2 * K) if c == 'B' else (int(y) + K) % (2 * K)
    black_desires.append((x, y))

cuml_2D = [[0] * (2*K) for _ in range(2*K)]
for x, y in black_desires:
    cuml_2D[x][y] += 1

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


max_num = 0
for i in range(K):
    for j in range(K):
        current_num = sum_range_2D(cuml_2D, (i, j), K, K) \
                    + sum_range_2D(cuml_2D, (0, 0), i, j) \
                    + sum_range_2D(cuml_2D, (0, j + K), i, K - j) \
                    + sum_range_2D(cuml_2D, (i + K, 0), K - i, j) \
                    + sum_range_2D(cuml_2D, (i + K, j + K), K - i, K - j)
        max_num = max(max_num, current_num)

for i in range(K):
    for j in range(K, 2 * K):
        current_sum = sum_range_2D(cuml_2D, (i, j), K, 2 * K - j) \
                    + sum_range_2D(cuml_2D, (0, j - K), i, K) \
                    + sum_range_2D(cuml_2D, (i + K, j - K), K - i, K) \
                    + sum_range_2D(cuml_2D, (i, 0), K, j - K)
        max_num = max(max_num, current_num)
print(max_num)

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
d = []
for n in range(N):
    dd = input().split()
    x = int(dd[0])%(K)
    y = int(dd[1])%(K)
    c = dd[2]
    if (int(dd[0])//K+int(dd[1])//K) % 2 == 1:
        if c == "W":
            c = "B"
        else:
            c = "W"

    d.append([x,y,c])

def color(x,y,offsetX,offsetY,k):
    if ((x+offsetX)//k + (y+offsetY)//k) % 2 == 0:
        return "B"
    return "W"

def check(offsetX,offsetY,k):
    count = 0
    for a in d:
        r = color(a[0],a[1],offsetX,offsetY,k)
        if r == a[2]:
            count += 1
    return count

s = []
for i in range(K):
    for j in range(K):
        r = check(i,j,K)
        #print(i,j,r)
        s.append(r)

print(max(s))

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
d = []
for n in range(N):
    dd = input().split()
    d.append([int(dd[0]),int(dd[1]),dd[2]])

def color(x,y,offsetX,offsetY,k):
    if ((x+offsetX)//k + (y+offsetY)//k) % 2 == 0:
        return "B"
    return "W"

def check(offsetX,offsetY,k):
    count = 0
    for a in d:
        r = color(a[0],a[1],offsetX,offsetY,k)
        if r == a[2]:
            count += 1
    return count

s = []
for i in range(K*2):
    for j in range(K*2):
        r = check(i,j,K)
        print(i,j,r)
        s.append(r)

print(max(s))

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
d = []
for n in range(N):
    dd = input().split()
    d.append([int(dd[0]),int(dd[1]),dd[2]])

def color(x,y,offsetX,offsetY,k):
    if ((x+offsetX)/k + (y+offsetY)/k) % 2 == 0:
        return "B"
    return "W"

def check(offsetX,offsetY,k):
    count = 0
    for a in d:
        r = color(a[0],a[1],offsetX,offsetY,k)
        if r == a[2]:
            count += 1
    return count

s = []
for i in range(K*2):
    for j in range(K*2):
        s.append(check(i,j,K))

print(max(s))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
cum = [[0]*(2*K+1) for i in range(2*K+1)]

def vertex(z):
    if z < K:
        return [(0,z+1),(z+K,2*K)]
    else:
        return [(z-K-1,z+1)]

for i in range(N):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    x %= 2*K
    if c == 'B':
        y %= 2*K
    else:
        y += K
        y %= 2*K

    for d in [0,K]:
        for b,t in vertex((y+d)%(2*K)):
            for l,r in vertex((x+d)%(2*K)):
                cum[b][l] += 1
                cum[t][r] += 1
                cum[b][r] -= 1
                cum[t][l] -= 1

import numpy as np
cum = np.array(cum)
print(np.cumsum(np.cumsum(cum,axis=0),axis=1).max())

Submission status: Wrong Answer

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

MAP=[[0 for i in range(K*2+1)] for j in range(K*2+1)]
mod=K*2
for x,y,c in XYC:
    x=int(x)
    y=int(y)
    if c=="W":
        x+=K

    MAP[x%mod+1][y%mod+1]+=1
    MAP[(x+K)%mod+1][(y+K)%mod+1]+=1




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

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

ANS=0
for i in range(K):
    for j in range(K):
        print(i,j,MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j])
        if ANS<MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j]:
            ANS=MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j]
        if ANS<N-(MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j]):
            ANS=N-(MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j])
print(ANS)

Submission status: Wrong Answer

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

MAP=[[0 for i in range(K*2+1)] for j in range(K*2+1)]
mod=K*2
for x,y,c in XYC:
    x=int(x)
    y=int(y)
    if c=="W":
        x+=K

    MAP[x%mod+1][y%mod+1]+=1
    MAP[(x+K)%mod+1][(y+K)%mod+1]+=1

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

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

ANS=0
for i in range(K+1):
    for j in range(K+1):
        if ANS<MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j]:
            ANS=MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j]

print(ANS)

Submission status: Wrong Answer

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

MAP=[[0 for i in range(K*2+1)] for j in range(K*2+1)]
mod=K*2
for x,y,c in XYC:
    x=int(x)
    y=int(y)
    if c=="W":
        x+=K

    MAP[x%mod+1][y%mod+1]+=1

    x+=K
    y+=K

    MAP[x%mod+1][y%mod+1]+=1

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

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

ANS=0
for i in range(K+1):
    for j in range(K+1):
        if ANS<MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j]:
            ANS=MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j]

print(ANS)

Submission status: Wrong Answer

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

MAP=[[0 for i in range(K*2+1)] for j in range(K*2+1)]
mod=K*2
for x,y,c in XYC:
    x=int(x)
    y=int(y)
    if c=="W":
        x+=K

    MAP[x%mod+1][y%mod+1]+=1

    x+=K
    y+=K

    MAP[x%mod+1][y%mod+1]+=1

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

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

ANS=0
for i in range(K+1):
    for j in range(K+1):
        if ANS<MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j]:
            ANS=MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j]

print(ANS)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def cum_2d(field:list):
    row = len(field)
    col = len(field[0])
    
    # 横方向に累積和
    for r in range(row):
        for c in range(col-1):
            field[r][c+1] += field[r][c]
    
    # 縦方向に累積和
    for c in range(col):
        for r in range(row-1):
            field[r+1][c] += field[r][c]
            
    return field

n,k = li()

wishes = []
# mod K をとり、すべての希望を黒に変換
for _ in range(n):
    x,y,c = ls()
    x = int(x) % (2*k)
    y = int(y) % (2*k)
    
    if c == "B":
        if x >= k and y >= k:
            x -= k
            y -= k
        
        elif y >= k:
            x += k
            y -= k
    
    if c == "W":
        if x >= k and y >= k:
            y -= k
        
        elif x >= k:
            x -= k
            
        elif y >= k:
            y -= k
            
        else:
            x += k
        
    wishes.append((x,y))

imos = [[0 for _ in range(2*k+1)] for _ in range(2*k+1)]

for x, y in wishes:
    
    # xが K 未満のとき
    if x < k:
        # 左上
        imos[0][y+k+1] += 1
        imos[0][2*k] -= 1
        imos[x+1][y+k+1] -= 1
        imos[x+1][2*k] += 1
            
        # 左下
        imos[0][0] += 1
        imos[x+1][0] -= 1
        imos[0][y+1] -= 1
        imos[x+1][y+1] += 1
            
        # 中央
        imos[x+1][y+1] += 1
        imos[x+1][y+k+1] -= 1
        imos[x+k+1][y+1] -= 1
        imos[x+k+1][y+k+1] += 1
        
        # 右下
        imos[x+k+1][0] += 1
        imos[x+k+1][y+1] -= 1
        imos[2*k][0] -= 1
        imos[2*k][y+1] += 1
            
        # 右上
        imos[x+k+1][y+k+1] += 1
        imos[x+k+1][2*k] -= 1
        imos[2*k][y+k+1] -= 1
        imos[2*k][2*k] += 1

    # xが K 以上のとき
    else:
        #左
        imos[0][y+1] += 1
        imos[x-k+1][y+1] -= 1
        imos[0][y+k+1] -= 1
        imos[x-k+1][y+k+1] += 1
        
        # 下
        imos[x-k+1][0] += 1
        imos[x-k+1][y+1] -= 1
        imos[x+1][0] -= 1
        imos[x+1][y+1] += 1
        
        # 右
        imos[x+1][y+1] += 1
        imos[2*k][y+1] -= 1
        imos[x+1][y+k+1] -= 1
        imos[2*k][y+k+1] += 1
        
        # 上
        imos[x-k+1][y+k+1] += 1
        imos[x-k+1][2*k] -= 1
        imos[x+1][y+k+1] -= 1
        imos[x+1][2*k] += 1
    
    for row in range(2*k,-1,-1):
        print(imos[row])
        
    print()

# 累積和
imos = cum_2d(imos)
for row in range(2*k,-1,-1):
    print(imos[row])

ans = 0
for i in range(2*k):
    for j in range(2*k):
        if imos[i][j] > ans:
            ans = imos[i][j]
        

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def cum_2d(field:list):
    row = len(field)
    col = len(field[0])
    
    # 横方向に累積和
    for r in range(row):
        for c in range(col-1):
            field[r][c+1] += field[r][c]
    
    # 縦方向に累積和
    for c in range(col):
        for r in range(row-1):
            field[r+1][c] += field[r][c]
            
    return field

n,k = li()

wishes = []
# mod K をとり、すべての希望を黒に変換
for _ in range(n):
    x,y,c = ls()
    x = int(x) % k
    y = int(y) % k
    
    if c == "W":
        x += k
        
    wishes.append((x,y))

imos = [[0 for _ in range(2*k+1)] for _ in range(2*k+1)]

for x, y in wishes:
    
    # xが K 未満のとき
    if x < k:
        # 左上
        if y < k-1:
            imos[0][y+k+1] += 1
            imos[0][2*k] -= 1
            imos[x+1][y+k+1] -= 1
            imos[x+1][2*k] += 1
            
        # 左下
        if y > 0:
            imos[0][0] += 1
            imos[x+1][0] -= 1
            imos[0][y+1] -= 1
            imos[x+1][y+1] += 1
            
        # 中央
        imos[x+1][y+1] += 1
        imos[x+1][y+k+1] -= 1
        imos[x+k+1][y+1] -= 1
        imos[x+k+1][y+k+1] += 1
        
        # 右下
        if x < k-1:
            imos[x+k+1][0] += 1
            imos[x+k+1][y+1] -= 1
            imos[2*k][0] -= 1
            imos[2*k][y+1] += 1
            
        # 右上
        if x < k-1 and y < k:
            imos[x+k+1][y+k+1] += 1
            imos[x+k+1][2*k] -= 1
            imos[2*k][y+k+1] -= 1
            imos[2*k][2*k] += 1

    # xが K 以上のとき
    else:
        #左
        imos[0][y+1] += 1
        imos[x-k+1][y+1] -= 1
        imos[0][y+k+1] -= 1
        imos[x-k+1][y+k+1] += 1
        
        # 下
        imos[x-k+1][0] += 1
        imos[x-k+1][y+1] -= 1
        imos[x+1][0] -= 1
        imos[x+1][y+1] += 1
        
        # 右
        imos[x+1][y+1] += 1
        imos[2*k][y+1] -= 1
        imos[x+1][y+k+1] -= 1
        imos[2*k][y+k+1] += 1
        
        # 上
        imos[x-k+1][y+k+1] += 1
        imos[x-k+1][2*k] -= 1
        imos[x+1][y+k+1] -= 1
        imos[x+1][2*k] += 1
    


# 累積和
imos = cum_2d(imos)

ans = 0
for i in range(2*k):
    for j in range(2*k):
        if imos[i][j] > ans:
            ans = imos[i][j]
            
print(ans)

Submission status: Wrong Answer

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

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

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

def count(x1,x2,y1,y2):
    return grid[y1][x1] - grid[y1][x2] - grid[y2][x1] + grid[y2][x2]

ans = 0
for i in range(K+1):
    for j in range(K+1):
        tmp = count(j,j+K,i,i+K) + count(0,j,0,i) + count(j+K,2*K,0,i) +\
            count(0,j,i+K,2*K) + count(j+K,2*K,i+K,2*K)
        ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

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

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

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

def count(x1,x2,y1,y2):
    return grid[y1][x1] - grid[y1][x2] - grid[y2][x1] + grid[y2][x2]

ans = 0
for i in range(K):
    for j in range(K):
        tmp = count(j,j+K,i,i+K) + count(0,j,0,i) + count(j+K,2*K,0,i) +\
            count(0,j,i+K,2*K) + count(j+K,2*K,i+K,2*K)
        ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

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

for i in range(n):
    x, y, c = input().split()
    xyc.append([int(x), int(y), c])

L = k * 2
ans = 0
for a in range(k):
    for b in range(k):
        count = 0
        for x, y, c in xyc:
            if c == 'W':
                y += k
            if (x + a % L < k and y + b % L < k) or (x + a % L >= k and y + b % L >= k):
                count += 1

        ans = max(ans, count)

print(ans)

Submission status: Wrong Answer

Solution code:
R,r=range,raw_input
N,K=map(int,r().split())
L=K+1
P,Q=R(K),R(L)
D=[L*[0]for i in Q]
a=b=0
for i in R(N):
 x,y,c=r().split()
 x,y=int(x),int(y)
 p=(x/K+y/K+ord(c))%2
 D[y%K+1][x%K+1]+=1-2*p
 b+=p
for k in R(2):
 for i in P:
  for j in Q:D[(i+1,j)[k]][(j,i+1)[k]]+=D[i][j]
for i in Q:
 for j in Q:
  S=D[i][K]+D[K][j]-D[i][j]*2
  a=max(a,S,D[K][K]-S)
print a+b

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

N, K = map(int, raw_input().split())
DP = [[0] * (K + 1) for i in range(K + 1)]
bias = 0

for i in range(N):
    x, y, c = raw_input().split()
    x, y = int(x), int(y)
    c = (c == 'W')
    if (x / K + y / K + c) % 2 == 0:
        DP[y % K + 1][x % K + 1] += 1
    else:
        DP[y % K + 1][x % K + 1] -= 1
        bias += 1

for i in range(K):
    for j in range(K + 1):
        DP[i + 1][j] += DP[i][j]

for i in range(K + 1):
    for j in range(K):
        DP[i][j + 1] += DP[i][j]

ans = -(10 ** 9)

for i in range(K + 1):
    for j in range(K + 1):
        S = DP[i][j] * 2 + DP[K][K] - DP[i][K] - DP[K][j]
        ans = max(ans, S)

print ans + bias

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

N, K = map(int, raw_input().split())
DP = [[0] * (K + 1) for i in range(K + 1)]
bias = 0

for i in range(N):
    x, y, c = raw_input().split()
    x, y = int(x), int(y)
    c = (c == 'W')
    if (x / K + y / K + c) % 2 == 0:
        DP[y % K + 1][x % K + 1] += 1
    else:
        DP[y % K + 1][x % K + 1] -= 1
        bias += 1

for i in range(K):
    for j in range(K + 1):
        DP[i + 1][j] += DP[i][j]

for i in range(K + 1):
    for j in range(K):
        DP[i][j + 1] += DP[i][j]

ans = 0

for i in range(K + 1):
    for j in range(K + 1):
        S = DP[i][j] * 2 + DP[K][K] - DP[i][K] - DP[K][j]
        ans = max(ans, S)

print ans + bias

Submission status: Wrong Answer

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

s_in = lambda: stdin.readline()[:-1] # s = s_in()
d_in = lambda: int(stdin.readline()) # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split())) # List = ds_in()

N, K = ds_in()
checker = np.zeros((K*2+1, K*2+1))

for _ in range(N):
    x, y, c = s_in().split()
    x = int(x)
    y = int(y)
    parity = (x // K + y // K) % 2
    if c == 'W':
        if parity:
            checker[parity*K + x%K + 1, (1-parity)*K + y%K + 1] += 1
            checker[(1-parity)*K + x%K + 1, parity*K + y%K + 1] += 1
        else:
            checker[parity*K + x%K + 1, parity*K + y%K + 1] += 1
            checker[(1-parity)*K + x%K + 1, (1-parity)*K + y%K + 1] += 1
    else:
        if parity:
            checker[parity*K + x%K + 1, parity*K + y%K + 1] += 1
            checker[(1-parity)*K + x%K + 1, (1-parity)*K + y%K + 1] += 1
        else:
            checker[parity*K + x%K + 1, (1-parity)*K + y%K + 1] += 1
            checker[(1-parity)*K + x%K + 1, parity*K + y%K + 1] += 1
        
cum_c = np.cumsum(np.cumsum(checker, axis=0), axis=1)

ans = 0
for i in range(1, K+2):
    for j in range(1, K+2):
        ans = max(ans, cum_c[i+K-1, j+K-1] - cum_c[i-1, j+K-1] - cum_c[i+K-1, j-1] + cum_c[i-1, j-1])

print(int(ans))

Submission status: Wrong Answer

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

s_in = lambda: stdin.readline()[:-1] # s = s_in()
d_in = lambda: int(stdin.readline()) # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split())) # List = ds_in()

N, K = ds_in()
checker = np.zeros((K*2, K))


for _ in range(N):
    x, y, c = s_in().split()
    x = int(x)
    y = int(y)
    parity = (x // K + y // K) % 2
    if c == 'W':
        checker[parity*K + x%K, y%K] += 1
    else:
        checker[(1-parity)*K + x%K, y%K] += 1
        
# print(checker)
tot_c = np.concatenate((checker,\
        np.concatenate((checker[K:,:], checker[:K,:]), axis=0)), axis=1)
# print(tot_c)
cum_c = np.zeros((2*K + 1, 2*K + 1))
cum_c[1:, 1:] = np.cumsum(np.cumsum(tot_c, axis=0), axis=1)
# print(cum_c)

ans = 0
for i in range(1, K+2):
    for j in range(1, K+2):
        ans = max(ans, cum_c[i+K-1, j+K-1] - cum_c[i-1, j+K-1] - cum_c[i+K-1, j-1] + cum_c[i-1, j-1])

print(int(ans))

Submission status: Wrong Answer

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

s_in = lambda: stdin.readline()[:-1] # s = s_in()
d_in = lambda: int(stdin.readline()) # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split())) # List = ds_in()

N, K = ds_in()
checker = np.zeros((K*2, K))


for _ in range(N):
    x, y, c = s_in().split()
    x = int(x)
    y = int(y)
    parity = (x // K + y // K) % 2
    if c == 'W':
        checker[parity*K + x%K, y%K] += 1
    else:
        checker[(1-parity)*K + x%K, y%K] += 1
        
# print(checker)
tot_c = np.concatenate((checker,\
        np.concatenate((checker[K:,:], checker[:K,:]), axis=0)), axis=1)
# print(tot_c)
cum_c = np.zeros((2*K + 1, 2*K + 1))
cum_c[1:, 1:] = np.cumsum(np.cumsum(tot_c, axis=0), axis=1)
# print(cum_c)

ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        ans = max(ans, cum_c[i+K-1, j+K-1] - cum_c[i-1, j+K-1] - cum_c[i+K-1, j-1] + cum_c[i-1, j-1])

print(int(ans))

Submission status: Wrong Answer

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

s_in = lambda: stdin.readline()[:-1] # s = s_in()
d_in = lambda: int(stdin.readline()) # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split())) # List = ds_in()

N, K = ds_in()
checker = np.zeros((K*2, K))


for _ in range(N):
    x, y, c = s_in().split()
    x = int(x)
    y = int(y)
    parity = (x // K + y // K) % 2
    if c == 'W':
        checker[parity*K + x%K, y%K] += 1
    else:
        checker[(1-parity)*K + x%K, y%K] += 1
        
tot_c = np.concatenate((checker,\
        np.concatenate((checker[K:,:], checker[:K,:]), axis=0)), axis=1)
cum_c = np.zeros((2*K + 1, 2*K + 1))
cum_c[1:, 1:] = np.cumsum(np.cumsum(tot_c, axis=0), axis=1)

ans = 0
for i in range(K+1):
    for j in range(K+1):
        ans = max(ans, cum_c[i+K-1, j+K-1] - cum_c[i-1, j+K-1] - cum_c[i+K-1, j-1] + cum_c[i-1, j-1])

print(int(ans))

Submission status: Wrong Answer

Solution code:
N, K = [int(x) for x in input().split()]

table = [[0 for _ in range(K)] for _ in range(K)]

for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    
    if c == 'W':
        y = y+K
    
    x %= 2*K
    y %= 2*K
    
    table[x%K][y%K] += (-1)**(x//K + y//K)

for i in range(K-1, 0 ,-1):
    for j in range(K-1, -1, -1):
        table[i-1][j] += table[i][j]

for i in range(K-1, -1 ,-1):
    for j in range(K-1, 0, -1):
        table[i][j-1] += table[i][j]

max_ac = abs(table[0][0])

for i in range(1,K):
    accept1 = table[0][0] -2 * table[i][0]
    accept2 = table[0][0] -2 * table[0][i]
    max_ac = max(max_ac, abs(accept1), abs(accept2))

for i in range(1, K):
    for j in range(1, K):
        accept = table[0][0] -2*table[i][0] -2*table[0][j] + 2*table[i][j]
        max_ac = max(max_ac, abs(accept))

print(int((max_ac+N)//2))

Submission status: Wrong Answer

Solution code:
N, K = [int(x) for x in input().split()]

table = [[0 for _ in range(K)] for _ in range(K)]

for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    
    if c == 'W':
        y = y+K
    
    x %= 2*K
    y %= 2*K
    
    table[x%K][y%K] += (-1)**(x//K + y//K)

for i in range(K-1, 0 ,-1):
    for j in range(K-1, -1, -1):
        table[i-1][j] += table[i][j]

for i in range(K-1, -1 ,-1):
    for j in range(K-1, 0, -1):
        table[i][j-1] += table[i][j]

max_ac = abs(table[0][0])

for i in range(1,K):
    accept = table[0][0] - 2 * table[i][0]
    max_ac = max(max_ac, abs(accept))
for j in range(1,K):
    accept = table[0][0] -2 * table[0][j]
    max_ac = max(max_ac, abs(accept))

for i in range(1, K):
    for j in range(1, K):
        accept = table[0][0] -2*table[i][0] -2*table[0][j] + 2*table[i][j]
        max_ac = max(max_ac, abs(accept))

print(int((max_ac+N)/2))

Submission status: Wrong Answer

Solution code:
N, K = [int(x) for x in input().split()]

table = [[0 for _ in range(K)] for _ in range(K)]

for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    
    if c == 'W':
        y = y+K
    
    x %= 2*K
    y %= 2*K
    
    table[x%K][y%K] += (-1)**(x//K + y//K)

for i in range(K-1, 0 ,-1):
    for j in range(K-1, -1, -1):
        table[i-1][j] += table[i][j]

for i in range(K-1, -1 ,-1):
    for j in range(K-1, 0, -1):
        table[i][j-1] += table[i][j]

max_ac = table[0][0]

for i in range(1,K):
    accept = table[0][0] - 2 * table[i][0]
    max_ac = max(max_ac, abs(accept))
for j in range(1,K):
    accept = table[0][0] -2 * table[0][j]
    max_ac = max(max_ac, abs(accept))

for i in range(1, K):
    for j in range(1, K):
        accept = table[0][0] -2*table[i][0] -2*table[0][j] + 2*table[i][j]
        max_ac = max(max_ac, abs(accept))

print(int((max_ac+N)/2))

Submission status: Wrong Answer

Solution code:
N, K = [int(x) for x in input().split()]

table = [[0 for _ in range(K)] for _ in range(K)]

for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    
    if c == 'W':
        y = y+K
    
    x %= 2*K
    y %= 2*K
    
    table[x%K][y%K] += (-1)**(x//K + y//K)

for i in range(K-1, 0 ,-1):
    for j in range(K-1, -1, -1):
        table[i-1][j] += table[i][j]

for i in range(K-1, -1 ,-1):
    for j in range(K-1, 0, -1):
        table[i][j-1] += table[i][j]

accept = [[0 for _ in range(K)] for _ in range(K)]
accept[0][0] = table[0][0]
max_ac = accept[0][0]

for i in range(1,K):
    accept[i][0] = table[0][0] - 2 * table[i][0]
for j in range(1,K):
    accept[0][j] = table[0][0] -2 * table[0][j]

for i in range(1, K):
    for j in range(1, K):
        accept[i][j] = table[0][0] -2*table[i][0] -2*table[0][j] + 2*table[i][j]
        max_ac = max(max_ac, abs(accept[i][j]))
        
print(max_ac)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,k = (int(i) for i in input().split())
d = np.zeros((k+1,k+1),dtype=int)
def f(a,b):
	d[0][0]+=1
	d[a%k+1][b%k+1]+=2
	d[0][b%k+1]-=1
	d[a%k+1][0]-=1
def f2(a,b):
	d[a%k+1][b%k+1]-=2
	d[0][b%k+1]+=1
	d[a%k+1][0]+=1
for _ in range(n):
	x,y,c = (i for i in input().split())
	x,y = int(x)%(2*k),int(y)%(2*k)
	if c=="B": y = (y+k)%(2*k)
	if (x<k)^(y<k): f2(x,y)
	else: f(x,y)
d,ans = np.cumsum(np.cumsum(d,axis=0),axis=1),0
for i in range(k):
	for j in range(k): ans = max(ans,d[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,k = (int(i) for i in input().split())
d = np.zeros((k+1,k+1),dtype=int)
def f(a,b):
	d[0][0]+=1
	d[a%k+1][b%k+1]+=2
	d[0][b%k+1]-=1
	d[a%k+1][0]-=1
def f2(a,b):
	d[a%k+1][b%k+1]-=2
	d[0][b%k+1]+=1
	d[a%k+1][0]+=1
for _ in range(n):
	x,y,c = (i for i in input().split())
	x,y = int(x)%(2*k),int(y)%(2*k)
	if c=="W": y = (y+k)%(2*k)
	if (x<k)^(y<k): f2(x,y)
	else: f(x,y)
d,ans = np.cumsum(np.cumsum(d,axis=0),axis=1),0
for i in range(k):
	for j in range(k): ans = max(ans,d[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

N, K = map(int, input().split())
kk = K * 2


class CumSum2d(object):
    def __init__(self, H, W):
        self.H, self.W = H, W
        self.tiles = [[0] * W for _ in range(H)]

    def add(self, x, y, c=1):
        self.tiles[y][x] = c

    def build(self):
        for y in range(self.H):
            for x in range(1, self.W):
                self.tiles[y][x] += self.tiles[y][x - 1]
        for y in range(1, self.H):
            for x in range(self.W):
                self.tiles[y][x] += self.tiles[y - 1][x]

    def get(self, sx, sy, tx, ty):
        assert sx <= tx and sy <= ty
        cnt = self.tiles[ty][tx]
        if sx > 0:
            cnt -= self.tiles[ty][sx - 1]
        if sy > 0:
            cnt -= self.tiles[sy - 1][tx]
        if sx > 0 and sy > 0:
            cnt += self.tiles[sy - 1][sx - 1]
        return cnt


cs = CumSum2d(kk, kk)
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'B':
        y = y + K
    cs.add(x % kk, y % kk)
cs.build()

ans = 0
for x, y in product(range(K), repeat=2):
    cnt = 0
    cnt += cs.get(x, y, x + K - 1, y + K - 1)
    cnt += cs.get(x + K, y + K, kk - 1, kk - 1)
    if x > 0:
        cnt += cs.get(0, y + K, x - 1, kk - 1)
    if y > 0:
        cnt += cs.get(x + K, 0, kk - 1, y - 1)
    if x > 0 and y > 0:
        cnt += cs.get(0, 0, x - 1, y - 1)
    # print(cnt)
    ans = max(ans, cnt, N - cnt)
print(ans)