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:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,K = inpl()
grid_w = [[0 for i in range(K)] for j in range(K)]
grid_b = [[0 for i in range(K)] for j in range(K)]

for _ in range(N):
	x,y,c = inpl_str()
	x,y = int(x), int(y)
	dx,dy = x//K, y//K
	x,y = x%K,y%K

	if c == 'W':
		c = 1
	else:
		c = -1

	if (dx+dy)%2 != 0:
		c *= -1

	if c == 1:
		grid_w[y][x] += 1
	else:
		grid_b[y][x] += 1

grid_w_sum = [[0 for i in range(K+1)] for j in range(K)]
grid_b_sum = [[0 for i in range(K+1)] for j in range(K)]

for y in range(K):
	w_sum = 0
	b_sum = 0
	for x in range(K):
		w_sum += grid_w[y][x]
		b_sum += grid_b[y][x]
		grid_w_sum[y][x+1] = w_sum
		grid_b_sum[y][x+1] = b_sum


ans = 0
for ans_x in range(K+1):
	points = [[0,0] for i in range(K)]
	ans1 = 0
	for y in range(K):
		#左w,右b
		points[y][0] = grid_w_sum[y][ans_x] + (grid_b_sum[y][K]-grid_b_sum[y][ans_x])
		ans1 += points[y][0]
		#左b,右w
		points[y][1] = grid_b_sum[y][ans_x] + (grid_w_sum[y][K]-grid_w_sum[y][ans_x])


	for y in range(K):
		ans1 = ans1 + points[y][1] - points[y][0]
		ans = max(ans1,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
def m():
    n, k = map(int, input().split())
    grid = [[0 for _ in range(k*2)] for _ in range(k*2)]
    for _ in range(n):
        x, y, c = map(str, input().split())
        x, y = int(x), int(y)
        if c == "W":
            grid[x % (k * 2)][(y+k) % (k * 2)] +=1
        else:
            grid[x % (k * 2)][y% (k * 2)] += 1
        # grid.append((x % (k * 2), (y+k) % (k * 2)))

    accum = [[0] * (k * 2) for _ in range(k * 2)]

    accum[0][0] = grid[0][0]
    # x軸
    for j in range(1, k*2):
        accum[j][0] = grid[j][0] + accum[j - 1][0]

    for i in range(1, k*2):
        accum[0][i] = grid[0][i] + accum[0][i - 1]

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

    def query(sx, sy, gx, gy):
        if gx == -1 or gy == -1:
            return 0
        if sx == -1 and sy == -1:
            return accum[gx][gy]
        if sx == -1:
            return accum[gx][gy] - accum[gx][sy]
        if sy == -1:
            return accum[gx][gy] - accum[sx][gy]
        return accum[gx][gy] - accum[sx][gy] - accum[gx][sy] + accum[sx][sy]

    ans = 0
    MAX = k*2 -1
    MIN = -1
    for i in range(-1, MAX+1, 1):
        for j in range(-1, MAX+1, 1):
            cnt = 0
            cnt += query(i, j, min(i + k, MAX), min(j + k, MAX))
            cnt += query(min(i + k, MAX), max(j - k, MIN), min(i + k, MAX), min(j, MAX))
            cnt += query(min(i + k, MAX), min(j + k, MAX), min(i + k * 2, MAX), min(j + k * 2, MAX))
            cnt += query(max(i - k, MIN), min(j+k, MAX), i, min(j + k * 2, MAX))
            cnt += query(max(i-k, MIN), max(j-k, MIN), i, j)
            ans = max(cnt, ans)
    return ans

print(m())

Submission status: Wrong Answer

Solution code:
def m():
    n, k = map(int, input().split())
    grid = [[0 for _ in range(k*2)] for _ in range(k*2)]
    for _ in range(n):
        x, y, c = map(str, input().split())
        x, y = int(x), int(y)
        if c == "W":
            grid[x % (k * 2)][(y+k) % (k * 2)] +=1
        else:
            grid[x % (k * 2)][y% (k * 2)] += 1
        # grid.append((x % (k * 2), (y+k) % (k * 2)))

    accum = [[0] * (k * 2) for _ in range(k * 2)]

    accum[0][0] = grid[0][0]
    # x軸
    for j in range(1, k*2):
        accum[j][0] = grid[j][0] + accum[j - 1][0]

    for i in range(1, k*2):
        accum[0][i] = grid[0][i] + accum[0][i - 1]

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

    def query(sx, sy, gx, gy):
        if gx == -1 or gy == -1:
            return 0
        if sx == -1 and sy == -1:
            return accum[gx][gy]
        if sx == -1:
            return accum[gx][gy] - accum[gx][sy]
        if sy == -1:
            return accum[gx][gy] - accum[sx][gy]
        return accum[gx][gy] - accum[sx][gy] - accum[gx][sy] + accum[sx][sy]

    ans = 0
    MAX = k*2 -1
    MIN = -1
    for i in range(-1, MAX, 1):
        for j in range(-1, MAX, 1):
            cnt = 0
            cnt += query(i, j, min(i + k, MAX), min(j + k, MAX))
            cnt += query(min(i + k, MAX), max(j - k, MIN), min(i + k, MAX), min(j, MAX))
            cnt += query(min(i + k, MAX), min(j + k, MAX), min(i + k * 2, MAX), min(j + k * 2, MAX))
            cnt += query(max(i - k, MIN), min(j+k, MAX), i, min(j + k * 2, MAX))
            cnt += query(max(i-k, MIN), max(j-k, MIN), i, j)
            ans = max(cnt, ans)
    return ans

print(m())

Submission status: Wrong Answer

Solution code:
import numpy as np

n,k = map(int,input().split())
k2 = 2*k
point = []
tileMax = 0
while len(point) < n:
    X,Y,c = map(str, input().split())
    X = int(X)
    Y = int(Y)
    if(c == "W"):
        Y += k
    X,Y = X%k2,Y%k2
    point.append((X,Y))
tile = [[0 for _ in range(0,k2)] for _ in range(0,k2)]

for x,y in point:
    phase = x//k + y//k
    x,y = x%k,y%k
    if x==0 and y==0:
        if phase%2 == 0:
            tile[0][0] += 1
            tile[k][0] += -1
            tile[0][k] += -1
            tile[k][k] += 2
        if phase%2 == 1:
            tile[k][0] += 1
            tile[0][k] += 1
            tile[k][k] -= 2
    if x!=0 and y==0:
        if phase%2 == 0:
            tile[y][x] += 1
            tile[y][x+k] += -1
            tile[k][0] += 1
            tile[k][x] += -2
            tile[k][x+k] += 2
        if phase%2 == 1:
            tile[0][0] += 1
            tile[0][x] += -1
            tile[0][x+k] += 1
            tile[k][0] += -1
            tile[k][x] += 2
            tile[k][x+k] += -2
    if x==0 and y!=0:
        if phase%2 == 0:
            tile[0][x+k] += 1
            tile[y][x] += 1
            tile[y][x+k] += -2
            tile[y+k][x] += -1
            tile[y+k][x+k] += 2
        if phase%2 == 1:
            tile[0][0] += 1
            tile[0][x+k] += -1
            tile[y][x] += -1
            tile[y][x+k] += 2
            tile[y+k][x] += 1
            tile[y+k][x+k] += -2
    if x!=0 and y!=0:
        if phase%2 == 0:
            tile[0][0] += 1
            tile[0][x] += -1
            tile[0][x+k] += 1
            tile[y][0] += -1
            tile[y][x] += 2
            tile[y][x+k] += -2
            tile[y+k][0] += 1
            tile[y+k][x] += -2
            tile[y+k][x+k] += 2
        if phase%2 == 1:
            tile[0][x] += 1
            tile[0][x+k] += -1
            tile[y][0] += 1
            tile[y][x] += -2
            tile[y][x+k] += 2
            tile[y+k][0] += -1
            tile[y+k][x] += 2
            tile[y+k][x+k] += -2

ans = np.array(tile)
print(ans.max())

Submission status: Wrong Answer

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

d = [[0]*k for _ in range(k)]
for _ in xrange(n):
    x, y, c = raw_input().split()
    x, y = int(x), int(y)

    v = 1 if c == 'B' else -1
    if (x / k) % 2:
        v *= -1
    if (y / k) % 2:
        v *= -1

    d[x % k][y % k] += v

for i in xrange(k):
    for j in xrange(k):
        d[i][j] += (d[i-1][j] if i else 0)

max_ = 0
min_ = 0
for i in xrange(k):
    for j in xrange(k):
        d[i][j] += (d[i][j-1] if j else 0)
        if d[i][j] > max_:
            max_ = d[i][j]
        if d[i][j] < min_:
            min_ = d[i][j]

max_ = max_ * 2 - d[k-1][k-1]
min_ = min_ * 2 - d[k-1][k-1]

print (n + max(max_, -min_))/2

Submission status: Wrong Answer

Solution code:
n,k = (int(i) for i in input().split())
s,ans = [[0 for i in range(2*k)] for i in range(2*k)],0
def corner(a,b):
	s[a-k+1][b-k+1]+=1
	if a-k<-1 or b-k<-1: s[max(a-k+1,0)][max(b-k+1,0)]+=1
	if b!=2*k-1:
		s[a-k+1][b+1]-=1
		if a-k<-1: s[0][b+1]-=1
	if a!=2*k-1:
		s[a+1][b-k+1]-=1
		if b-k<-1: s[a+1][0]-=1
def pair(a,b):
	p = []
	for i in [a,b]:
		if i<k: p.append(i+k)
		else: p.append(i-k)
	return p
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)
	for i,j in [[x,y],pair(x,y)]: corner(i,j)
for i in range(2*k):
	for j in range(1,2*k): s[i][j]+=s[i][j-1]
for j in range(2*k):
	for i in range(1,2*k): s[i][j]+=s[i-1][j]
for i in range(2*k): ans = max(ans,max(s[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

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


class RectangleSum(object):
    def __init__(self, dat, H, W):
        self.H = H
        self.W = W
        self.sum = [[0 for _ in range(W)] for _ in range(H)]
        for y in range(H):
            for x in range(W):
                self.sum[y][x] = dat[y][x]
                if y > 0:
                    self.sum[y][x] += self.sum[y - 1][x]
                if x > 0:
                    self.sum[y][x] += self.sum[y][x - 1]
                if y > 0 and x > 0:
                    self.sum[y][x] -= self.sum[y - 1][x - 1]

    def get(self, left, top, right, buttom):
        val = self.sum[buttom][right]
        if left > 0:
            val -= self.sum[buttom][left - 1]
        if top > 0:
            val -= self.sum[top - 1][right]
        if left > 0 and top > 0:
            val += self.sum[top - 1][left - 1]
        return val


rs = RectangleSum(data, K2, K2)
for x, y in product(range(K), range(K)):
    ans = rs.get(x, y, x + K - 1, y + K - 1) + \
        rs.get(x + K, y + K, K2 - 1, K2 - 1)
    if x > 0:
        ans += rs.get(0, K, x - 1, K2 - 1)
    if y > 0:
        ans += rs.get(K, 0, K2 - 1, y - 1)
    if x > 0 and y > 0:
        ans += rs.get(0, 0, x - 1, y - 1)
    # print('x={}, y={}, ans={}'.format(x, y, ans))
    if ans == N:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

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


def is_black(x, y, cx, cy):
    if 0 <= x < cx and 0 <= y < cy:
        return True
    elif 0 <= x < cx and cy + K <= y < cy + 2 * K:
        return True
    elif cx + K <= x < cx + 2 * K and 0 <= y < cy:
        return True
    elif cx <= x < cx + K and cy <= y < cy + K:
        return True
    elif cx + K <= x < cx + 2 * K and cy + K <= y < cy + 2 * K:
        return True
    else:
        return False


for cx, cy in product(range(K), range(K)):
    ans = 0
    for x, y in data:
        if is_black(x, y, cx, cy):
            ans += 1
    if ans == N:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

N, K = map(int, input().split())
data = [0] * N
for i in range(N):
    tmp = input().split()
    data[i] = int(tmp[0]), int(tmp[1]), tmp[2]


def is_same_color(x, y, c):
    a = x // K % 2
    b = y // K % 2
    if a + b == 1:
        return 'W' == c
    else:
        return 'B' == c


for cx, cy in product(range(K), range(K)):
    ans = 0
    for d in data:
        x, y, c = d
        if is_same_color(x + cx, y + cy, c):
            ans += 1
    ans = max(ans, N - ans)
    if ans == N:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

N, K = map(int, input().split())
data = [0] * N
for i in range(N):
    tmp = input().split()
    data[i] = int(tmp[0]), int(tmp[1]), tmp[2]


def color(x, y, cx, cy):
    a = (x + cx) // K % 2
    b = (y + cy) // K % 2
    if a == 0 and b == 0:
        return 'W'
    elif a == 1 and b == 1:
        return 'W'
    else:
        return 'B'


for cx, cy in product(range(K), range(K)):
    ans = 0
    for d in data:
        x, y, c = d
        if c == color(x, y, cx, cy):
            ans += 1
    if ans == N:
        break
    ans = max(ans, N - ans)
print(ans)

Submission status: Wrong Answer

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

xy = []
F = [[0]*(2*k+1) for _ in range(2*k+1)]
for _ in range(n):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'B':
        y += k
    if y%(2*k) >= k:
        x += k
    x %= 2*k
    y = y%k+k

    for i in range(2):
        x = (x+i*k)%(2*k)
        y = (y+i*k)%(2*k)
    #右上
    F[y+1][x+1] += 1
    if x-k >= 0 and y-k >= 0:
        #普通の左上と左上右下
        F[y+1][x-k+1] -= 1
        F[y-k+1][x+1] -= 1
        F[y-k+1][x-k+1] += 1
    elif y-k >= 0:
        #特殊な左
        F[y-k+1][0] += 1
        F[y+1][0] -= 1
        F[y-k+1][x+1] -= 1
        #特殊な左上と左下
        F[y-k+1][x+k+1] += 1
        F[y+1][x+k+1] -= 1
    elif x-k >= 0:
        F[0][x-k+1] += 1
        F[0][x+1] -= 1
        F[y+1][y-k+1] -= 1

        F[y+k+1][x-k+1] += 1
        F[y+k+1][x+1] -=1
    else:
        F[0][x+1] -= 1
        F[y+1][0] -= 1
        F[0][0] += 1
        #左上
        F[y+k+1][0] += 1
        F[y+k+1][x+1] -= 1
        #右下
        F[0][x+k+1] += 1
        F[y+1][x+k+1] -= 1
        #右上
        F[y+k+1][x+k+1] += 1

    #print("~~~~~~~~~~~~~~~~~~~")
    #print(*reversed(F[:-1]), sep="\n")
ans = 0
m = 3

from numpy import array
F = array(F)
for i in range(0, 2*k):
    F[:, i+1] += F[:, i]
for i in range(0, 2*k):
    F[i+1, :] += F[i, :]
print(F[:2*k, :2*k].max())

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    checklist = [[0]*(2*K) for i in range(2*K)]
    for i in range(N):
        x, y, c = input().split(" ")
        x = int(x)
        y = int(y)
        if c == "B":
            checklist[x % (2*K)][y % (2*K)] += 1
        else:
            checklist[x % (2*K)][(y+K) % (2*K)] += 1
    checksum = [[0]*(2*K) for i in range(2*K)]
    i = 0
    for i in range(2*K):
        if i == 0:
            checksum[0][0] = checklist[0][0]
        else:
            for j in range(i+1):
                if j < i:
                    if j > 0:
                        checksum[j][i] = checksum[j][i-1] + checksum[j-1][i] - checksum[j-1][i-1] + checklist[j][i]
                    else:
                        checksum[j][i] = checksum[j][i-1] + checklist[j][i]
                else:
                    for k in range(i+1):
                        if k > 0:
                            checksum[i][k] = checksum[i-1][k] + checksum[i][k-1] - checksum[i-1][k-1] + checklist[i][k]
                        else:
                            checksum[i][k] = checksum[i-1][k] + checklist[i][k]
    ans = 0
    for i in range(2*K):
        for j in range(2*K-i):
            if i <= K and j <= K:
                sq1 = checksum[i+K-1][j+K-1]
                if i > 0 and j > 0:
                    sq1 = checksum[i+K-1][j+K-1] - checksum[i-1][j+K-1] - checksum[i+K-1][j-1] + checksum[i-1][j-1]
                elif i > 0:
                    sq1 = checksum[i+K-1][j+K-1] - checksum[i-1][j+K-1]
                elif j > 0:
                    sq1 = checksum[i+K-1][j+K-1] - checksum[i+K-1][j-1]
                sq2 = 0
                if i > 0 and j > 0:
                    sq2 = checksum[i-1][j-1]
                sq3 = 0
                if i < 2*K-1 and j > 0:
                    sq3 = checksum[2*K-1][j-1] - checksum[i+K-1][j-1]
                sq4 = 0
                if i > 0 and j < 2*K-1:
                    sq4 = checksum[i-1][2*K-1] - checksum[i-1][j+K-1]
                sq5 = 0
                if i < 2*K-1 and j < 2*K-1:
                    sq5 = checksum[2*K-1][2*K-1] - checksum[2*K-1][j+K-1] - checksum[i+K-1][2*K-1] + checksum[i+K-1][j+K-1]
                ans = max(ans, sq1+sq2+sq3+sq4+sq5)
            elif i <= K:
                sq1 = checksum[i+K-1][2*K-1] - checksum[i+K-1][j-1]
                if i > 0:
                    sq1 = checksum[i+K-1][2*K-1] - checksum[i-1][2*K-1] - checksum[i+K-1][j-1] + checksum[i-1][j-1]
                sq2 = 0
                if i > 0:
                    sq2 = checksum[i-1][j-1] - checksum[i-1][j-K-1]
                sq3 = checksum[2*K-1][j-1] - checksum[i+K-1][j-1] - checksum[2*K-1][j-K-1] + checksum[i+K-1][j-K-1]
                sq4 = checksum[i+K-1][j-K-1]
                if i > 0:
                    sq4 = checksum[i+K-1][j-K-1] - checksum[i-1][j-K-1]
                ans = max(ans, sq1+sq2+sq3+sq4)
            elif j <= K:
                sq1 = checksum[2*K-1][j+K-1] - checksum[i-1][j+K-1]
                if j > 0:
                    sq1 = checksum[2*K-1][j+K-1] - checksum[2*K-1][j-1] - checksum[i-1][j+K-1] + checksum[i-1][j-1]
                sq2 = 0
                if j > 0:
                    sq2 = checksum[i-1][j-1] - checksum[i-K-1][j-1]
                sq3 = checksum[i-1][2*K-1] - checksum[i-1][j+K-1] - checksum[i-K-1][2*K-1] + checksum[i-K-1][j+K-1]
                sq4 = checksum[i-K-1][j+K-1]
                if j > 0:
                    sq4 = checksum[i-K-1][j+K-1] - checksum[i-K-1][j-1]
                ans = max(ans, sq1+sq2+sq3+sq4)
            if ans == N:
                break
        if ans == N:
            break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    checklist = [[0]*(2*K) for i in range(2*K)]
    for i in range(N):
        x, y, c = input().split(" ")
        x = int(x)
        y = int(y)
        if c == "B":
            checklist[x % (2*K)][y % (2*K)] += 1
        else:
            checklist[x % (2*K)][(y+K) % (2*K)] += 1
    checksum = [[0]*(2*K) for i in range(2*K)]
    i = 0
    for i in range(2*K):
        if i == 0:
            checksum[0][0] = checklist[0][0]
        else:
            for j in range(i+1):
                if j < i:
                    if j > 0:
                        checksum[j][i] = checksum[j][i-1] + checksum[j-1][i] - checksum[j-1][i-1] + checklist[j][i]
                    else:
                        checksum[j][i] = checksum[j][i-1] + checklist[j][i]
                else:
                    for k in range(i+1):
                        if k > 0:
                            checksum[i][k] = checksum[i-1][k] + checksum[i][k-1] - checksum[i-1][k-1] + checklist[i][k]
                        else:
                            checksum[i][k] = checksum[i-1][k] + checklist[i][k]
    ans = 0
    for i in range(2*K):
        for j in range(2*K-i):
            if i <= K and j <= K:
                sq1 = checksum[i+K-1][j+K-1]
                if i > 0 and j > 0:
                    sq1 = checksum[i+K-1][j+K-1] - checksum[i-1][j+K-1] - checksum[i+K-1][j-1] + checksum[i-1][j-1]
                elif i > 0:
                    sq1 = checksum[i+K-1][j+K-1] - checksum[i-1][j+K-1]
                elif j > 0:
                    sq1 = checksum[i+K-1][j+K-1] - checksum[i+K-1][j-1]
                sq2 = 0
                if i > 0 and j > 0:
                    sq2 = checksum[i-1][j-1]
                sq3 = 0
                if i < 2*K-1 and j > 0:
                    sq3 = checksum[2*K-1][j-1] - checksum[i+K-1][j-1]
                sq4 = 0
                if i > 0 and j < 2*K-1:
                    sq4 = checksum[i-1][2*K-1] - checksum[i-1][j+K-1]
                sq5 = 0
                if i < 2*K-1 and j < 2*K-1:
                    sq5 = checksum[2*K-1][2*K-1] - checksum[2*K-1][j+K-1] - checksum[i+K-1][2*K-1] + checksum[i+K-1][j+K-1]
                ans = max(ans, sq1+sq2+sq3+sq4+sq5)
            elif i <= K:
                sq1 = checksum[i+K-1][2*K-1] - checksum[i+K-1][j-1]
                if i > 0:
                    sq1 = checksum[i+K-1][2*K-1] - checksum[i-1][2*K-1] - checksum[i+K-1][j-1] + checksum[i-1][j-1]
                sq2 = 0
                if i > 0:
                    sq2 = checksum[i-1][j-1] - checksum[i-1][j-K-1]
                sq3 = checksum[2*K-1][j-1] - checksum[i+K-1][j-1] - checksum[2*K-1][j-K-1] + checksum[i+K-1][j-K-1]
                sq4 = checksum[i+K-1][j-K-1]
                if i > 0:
                    sq4 = checksum[i+K-1][j-K-1] - checksum[i-1][j-K-1]
                ans = max(ans, sq1+sq2+sq3+sq4)
            elif j <= K:
                sq1 = checksum[2*K-1][j+K-1] - checksum[i-1][j+K-1]
                if j > 0:
                    sq1 = checksum[2*K-1][j+K-1] - checksum[2*K-1][j-1] - checksum[i-1][j+K-1] + checksum[i-1][j-1]
                sq2 = 0
                if j > 0:
                    sq2 = checksum[i-1][j-1] - checksum[i-K-1][j-1]
                sq3 = checksum[i-1][2*K-1] - checksum[i-1][j+K-1] - checksum[i-K-1][2*K-1] + checksum[i-K-1][j+K-1]
                sq4 = checksum[i-K-1][j+K-1]
                if j > 0:
                    sq4 = checksum[i-K-1][j+K-1] - checksum[i-K-1][j-1]
                ans = max(ans, sq1+sq2+sq3+sq4)
            if ans == N:
                break
        if ans == N:
            break
    print(ans)

Submission status: Wrong Answer

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

a=[]
for i in range(N):
	x,y,c=raw_input().split()
	x=int(x)
	y=int(y)
	if c=="W": a.append( ( (x+K)%(2*K) , y%(2*K) ) )
	else: a.append( (x%(2*K) ,y%(2*K)) )


s=[ [ 0 for i in range(4*K) ] for j in range(4*K) ]
w=[ [ None for i in range(4*K) ] for j in range(4*K) ]


for x,y in a:
	s[x][y]+=1



for y in range(4*K):
	for x in range(4*K):
		if x==0: w[x][y]=s[x][y]
		else:
			w[x][y]=w[x-1][y]+s[x][y]

for x in range(4*K):
	for y in range(4*K-1,-1,-1):
		if y==4*K-1: w[x][y]=w[x][y]
		else: w[x][y]=w[x][y+1]+w[x][y]



def calc(x,y):
	if x<0 or y<0:
		return 0
	if y+K>4*K-1:
		return w[x][y]-w[x-K][y]
	elif x-K<0:
		return w[x][y]-w[x][y+K]		
	else:
		return w[x][y]-w[x-K][y]-w[x][y+K]+w[x-K][y+K]

ans=0
for x in range(K*2):
	for y in range(K*2):
		tmp=calc(x,y)+calc(x+K,y+K)+calc(x+2*K,y+2*K)+calc(x-K,y-K)+calc(x-2*K,y-2*K)+calc(x+K,y-K)+calc(x+K,y-2*K)+calc(x-K,y+K)+calc(x-2*K,y+2*K)+calc(x+2*K,y)+calc(x-2*K,y)+calc(x,y+2*K)+calc(x,y-2*K)
		ans=max(ans,tmp)

print ans

Submission status: Wrong Answer

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

a=[]
for i in range(N):
	x,y,c=raw_input().split()
	x=int(x)
	y=int(y)
	if c=="W": a.append( ( (x+K)%(2*K) , y%(2*K) ) )
	else: a.append( (x%(2*K) ,y%(2*K)) )


s=[ [ 0 for i in range(4*K) ] for j in range(4*K) ]
w=[ [ None for i in range(4*K) ] for j in range(4*K) ]


for x,y in a:
	s[x][y]+=1



for y in range(4*K):
	for x in range(4*K):
		if x==0: w[x][y]=s[x][y]
		else:
			w[x][y]=w[x-1][y]+s[x][y]

for x in range(4*K):
	for y in range(4*K-1,-1,-1):
		if y==4*K-1: w[x][y]=w[x][y]
		else: w[x][y]=w[x][y+1]+w[x][y]



def calc(x,y):
	if x<0 or y<0:
		return 0
	if y+K>4*K-1:
		return w[x][y]-w[x-K][y]
	elif x-K<0:
		return w[x][y]-w[x][y+K]		
	else:
		return w[x][y]-w[x-K][y]-w[x][y+K]+w[x-K][y+K]

ans=0
for x in range(K*2):
	for y in range(K*2):
		tmp=calc(x,y)+calc(x+2*K,y)+calc(x+K,y+K)+calc(x,y+2*K)+calc(x+2*K,y+2*K)+calc(x-2*K,y)+calc(x-K,y-K)+calc(x,y-2*K)+calc(x-2*K,y-2*K)
		ans=max(ans,tmp)

print ans

Submission status: Wrong Answer

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

a=[]
for i in range(N):
	x,y,c=raw_input().split()
	x=int(x)
	y=int(y)
	if c=="W": a.append( ( (x+K)%(2*K) , y%(2*K) ) )
	else: a.append( (x%(2*K) ,y%(2*K)) )


s=[ [ 0 for i in range(4*K) ] for j in range(4*K) ]
w=[ [ None for i in range(4*K) ] for j in range(4*K) ]


for x,y in a:
	s[x][y]+=1



for y in range(4*K):
	for x in range(4*K):
		if x==0: w[x][y]=s[x][y]
		else:
			w[x][y]=w[x-1][y]+s[x][y]

for x in range(4*K):
	for y in range(4*K-1,-1,-1):
		if y==4*K-1: w[x][y]=w[x][y]
		else: w[x][y]=w[x][y+1]+w[x][y]



def calc(x,y):
	if y+K>4*K-1:
		return w[x][y]-w[x-K][y]
	elif x-K<0:
		return w[x][y]-w[x][y+K]		
	else:
		return w[x][y]-w[x-K][y]-w[x][y+K]+w[x-K][y+K]

ans=0
for x in range(K*2):
	for y in range(K*2):
		tmp=calc(x,y)+calc(x+2*K,y)+calc(x+K,y+K)+calc(x,y+2*K)+calc(x+2*K,y+2*K)
		ans=max(ans, max(tmp,N-tmp))

print ans

Submission status: Wrong Answer

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

a=[]
for i in range(N):
	x,y,c=raw_input().split()
	x=int(x)
	y=int(y)
	if c=="W": a.append( ( (x+K)%(2*K) , y%(2*K) ) )
	else: a.append( (x%(2*K) ,y%(2*K)) )


s=[ [ 0 for i in range(4*K) ] for j in range(4*K) ]
w=[ [ None for i in range(4*K) ] for j in range(4*K) ]


for x,y in a:
	s[x][y]+=1



for y in range(4*K):
	for x in range(4*K):
		if x==0: w[x][y]=s[x][y]
		else:
			w[x][y]=w[x-1][y]+s[x][y]

for x in range(4*K):
	for y in range(4*K-1,-1,-1):
		if y==4*K-1: w[x][y]=w[x][y]
		else: w[x][y]=w[x][y+1]+w[x][y]



def calc(x,y):
	if y+K>4*K-1:
		return w[x][y]-w[x-K][y]
	elif x-K<0:
		return w[x][y]-w[x][y+K]		
	else:
		return w[x][y]-w[x-K][y]-w[x][y+K]+w[x-K][y+K]

ans=0
for x in range(K*2):
	for y in range(K*2):
		tmp=calc(x,y)+calc(x+2*K,y)+calc(x+K,y+K)+calc(x,y+2*K)+calc(x+2*K,y+2*K)
		ans=max(ans,tmp)

print ans

Submission status: Wrong Answer

Solution code:
import itertools
from collections import defaultdict
N,K=map(int,raw_input().split())

a=[]
for i in range(N):
	x,y,c=raw_input().split()
	x=int(x)
	y=int(y)
	if c=="W": a.append( ( (x+K)%(2*K)+K , y%(2*K)+K ) )
	else: a.append( (x%(2*K)+K ,y%(2*K)+K) )
	#if c=="W": a.append( ( (x+K)%(2*K) , y%(2*K) ) )
	#else: a.append( (x%(2*K) ,y%(2*K)) )



s=defaultdict(lambda: 0)
w=defaultdict(lambda: 0)


for x,y in a:
	s[(x,y)]+=1



for y in range(4*K):
	for x in range(4*K):
		if x==0: w[(x,y)]=s[(x,y)]
		else: w[(x,y)]=w[(x-1,y)]+s[(x,y)]



for x in range(4*K):
	for y in range(4*K-1,-1,-1):
		if y==4*K-1: w[(x,y)]=w[(x,y)]
		else: w[(x,y)]=w[(x,y+1)]+w[(x,y)]


def calc(x1,y1):
	return w[(x1,y1)]-w[(x1-K,y1)]-w[(x1,y1+K)]+w[(x1-K,y1+K)]


b=[]
ans=0

for x in range(K,3*K):
	for y in range(K,3*K):
		ans=max(ans, calc(x,y)+calc(x+K,y+K))

print ans

Submission status: Wrong Answer

Solution code:
import itertools
from collections import defaultdict
N,K=map(int,raw_input().split())

a=[]
for i in range(N):
	x,y,c=raw_input().split()
	x=int(x)
	y=int(y)
	if c=="W": a.append( ( (x+K)%(2*K)+K , y%(2*K)+K ) )
	else: a.append( (x%(2*K)+K ,y%(2*K)+K) )
	#if c=="W": a.append( ( (x+K)%(2*K) , y%(2*K) ) )
	#else: a.append( (x%(2*K) ,y%(2*K)) )



s=defaultdict(lambda: 0)
w=defaultdict(lambda: 0)


for x,y in a:
	s[(x,y)]+=1



for y in range(4*K):
	for x in range(4*K):
		if x==0: w[(x,y)]=s[(x,y)]
		else: w[(x,y)]=w[(x-1,y)]+s[(x,y)]



for x in range(4*K):
	for y in range(4*K-1,-1,-1):
		if y==4*K-1: w[(x,y)]=w[(x,y)]
		else: w[(x,y)]=w[(x,y+1)]+w[(x,y)]


def calc(x1,y1):
	#if x1<0 or y1<0:
	#	return 0
	if 0<= x1-K < 4*K and 0<= y1+K < 4*K:
		return w[(x1,y1)]-w[(x1-K,y1)]-w[(x1,y1+K)]+w[(x1-K,y1+K)]
	else:
		return 0

b=[]
ans=0
combi=list(itertools.product([-1,1], repeat=2))

for x in range(K,3*K):
	for y in range(K,3*K):
		ans=0
		ans+=calc(x,y)
		for dx,dy in combi:
			ans+=calc(x+K*dx, y+K*dy)

		ans+=calc(x, y+2*K)
		ans+=calc(x, y-2*K)
		b.append(ans)

print max(b)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
v = []
for i in range(n):
    abc = [x for x in input().split()]
    a = int(abc[0])
    b = int(abc[1])
    c = abc[2]
    if c == 'W':
        b += k
    v.append((a % (2*k), b % (2*k)))

s = [[0 for _ in range(3*k+1)] for _ in range(3*k+1)]
s2 = [[0 for _ in range(k+1)] for _ in range(k+1)]
s3 = [[0 for _ in range(k+1)] for _ in range(k+1)]

for i in range(n):
    s[v[i][1]][v[i][0]] += 1
    s[v[i][1]+k][v[i][0]+k] += 1
    s[v[i][1]+k][v[i][0]] -= 1
    s[v[i][1]][v[i][0]+k] -= 1

for i in range(3*k):
    for j in range(3*k):
        s[i+1][j] += s[i][j]
for i in range(3*k):
    for j in range(3*k):
        s[i][j+1] += s[i][j]

for i in range(3*k):
    for j in range(3*k):
        c = (i//k+j//k) % 2
        if c == 0:
            s2[i % k][j % k] += s[i][j]
        else:
            s3[i % k][j % k] += s[i][j]
res = 0

for i in range(k):
    for j in range(k):
        #res = max(res, s2[i][j])
        res = max(res, s3[i][j])

print(res)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
v = []
for i in range(n):
    abc = [x for x in input().split()]
    a = int(abc[0])
    b = int(abc[1])
    c = abc[2]
    if c == 'W':
        b += k
    v.append((a % (2*k), b % (2*k)))

s = [[0 for _ in range(3*k+1)] for _ in range(3*k+1)]
s2 = [[0 for _ in range(k+1)] for _ in range(k+1)]
s3 = [[0 for _ in range(k+1)] for _ in range(k+1)]

for i in range(n):
    s[v[i][1]][v[i][0]] += 1
    s[v[i][1]+k][v[i][0]+k] += 1
    s[v[i][1]+k][v[i][0]] -= 1
    s[v[i][1]][v[i][0]+k] -= 1

for i in range(3*k):
    for j in range(3*k):
        s[i+1][j] += s[i][j]
for i in range(3*k):
    for j in range(3*k):
        s[i][j+1] += s[i][j]

for i in range(3*k):
    for j in range(3*k):
        c = (i//k+j//k) % 2
        if c == 0:
            s2[i % k][j % k] += s[i][j]
        else:
            s3[i % k][j % k] += s[i][j]
res = 0

for i in range(k):
    for j in range(k):
        res = max(res, s2[i][j])
        # res = max(res, s3[i][j])
print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np

class Check:
	def __init__(self, k, c):
		self.k = k
		self.c = c
		self.m = np.zeros([k+1, k+1])

	def add_desire(self, x, y, c):
		cx = x + 1
		cy = y + 1

		if c == self.c:
			self.m[cx:, cy:] += 1.
			self.m[:cx, :cy] += 1.
		else:
			self.m[cx:, :cy] += 1.
			self.m[:cx, cy:] += 1.

	def get_max(self):
		return int(np.asscalar(self.m.max()))

n, k = map(int, input().split())
lines = [input() for _ in range(n)]

checkW = Check(k, "W")

for line in lines:
	x, y, c = line.split()
	x = int(x)
	y = int(y)

	x = -1*x+k-1 if x<0 else x
	y = -1*y+k-1 if y<0 else y
	
	bigX = x//k
	bigY = y//k

	localX = x%k
	localY = y%k
	localC = c

	if ((bigX + bigY) % 2) != 0:
		localC = "W" if localC == "B" else "B"
		
	checkW.add_desire(localX, localY, localC)

print(checkW.get_max())