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())
x, y, c = [0] * N, [0] * N, [0] * N
board = [[0] * (2 * K + 1) for i in range(2 * K + 1)]
MOD = 2 * K + 1
for i in range(N):
    x[i], y[i], c[i] = input().split()
    x[i], y[i] = int(x[i]), int(y[i])
    if c[i] == 'W':
        x[i] += K
        c[i] = 'B'
    x[i] %= 2 * K
    y[i] %= 2 * K
    board[y[i]+1][x[i]+1] += 1

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

# for i in range(2*K+1):
#     print(' '.join(map(str, board[i])))
ans = 0
def c(x1, y1):
    global K, board
    x1 %= MOD
    y1 %= MOD
    x2 = (x1 + K) % MOD
    y2 = (y1 + K) % MOD
    if x1 < x2:
        x11, x12, x21, x22 = x1, x2, 0, 0
    else:
        x11, x12, x21, x22 = x1, 2*K, 0, x2
    if y1 < y2:
        y11, y12, y21, y22 = y1, y2, 0, 0
    else:
        y11, y12, y21, y22 = y1, 2*K, 0, y2
    f = lambda a, b, c, d: board[a][b] + board[c][d]\
            - board[a][d] - board[c][b]
    # print("x11: %d, x12: %d" % (x11, x12))
    # print("x21: %d, x22: %d" % (x21, x22))
    # print("y11: %d, y12: %d" % (y11, y12))
    # print("y21: %d, y22: %d" % (y21, y22))
    # print("a1: %d" % f(y12, x12, y11, x11))
    # print("a2: %d" % f(y22, x22, y21, x21))
    return f(y12, x12, y11, x11) + f(y22, x22, y21, x21)


for i in range(K+1):
    for j in range(K+1):
        # print('c(i, j): %d' % c(i, j))
        # print('c(i+K, j+K): %d' % c(i+K, j+K))
        # print('')
        ans = max((ans, c(i, j) + c(i+K, j+K)))

print(ans)

Submission status: Wrong Answer

Solution code:
def get_while(n):
    ans = []
    for _ in range(n):
       ans += [input().split(" ")]
    return ans

def solve(n, k, inputs_):
    inputs = list(inputs_)
    inputs = [[int(i[0]) % (2 * k), int(i[1]) % (2 * k), i[2]] for i in inputs]
    points = [[i[0], i[1] + k if i[2] == 'W' else 0] for i in inputs]
    ans = 0
    for x in range(k):
        for y in range(k):
            interim_ans = 0
            for p in points:
                p = [(p[0] - x) % (2 * k), (p[1] - y) % (2 * k)]
                condition = (0 <= p[0] <= (k - 1) and 0 <= p[1] <= (k - 1)) or (k <=  p[0] <=  (2 * k - 1) and k <= p[1] <= (2 * k - 1))
                if condition:
                    interim_ans = interim_ans + 1
            if interim_ans > ans:
                ans = interim_ans
    return ans

if __name__ == '__main__':
    n, k = list(map(lambda x: int(x), input().split(" ")))
    inputs = get_while(n)
    print(solve(n, k, inputs))

Submission status: Wrong Answer

Solution code:
def get_while(n):
    ans = []
    for _ in range(n):
       ans += [input().split(" ")]
    return ans

def solve(n, k, inputs_):
    inputs = list(inputs_)
    inputs = [[int(i[0]) % (2 * k), int(i[1]) % (2 * k), i[2]] for i in inputs]
    points = [[i[0], i[1] + k if i[2] == 'W' else 0] for i in inputs]
    ans = 0
    for x in range(2 * k):
        for y in range(2 * k):
            interim_ans = 0
            for p in points:
                p = [(p[0] - x) % (2 * k), (p[1] - y) % (2 * k)]
                condition = (0 <= p[0] <= (k - 1) and 0 <= p[1] <= (k - 1)) or (k <=  p[0] <=  (2 * k - 1) and k <= p[1] <= (2 * k - 1))
                if condition:
                    interim_ans = interim_ans + 1
            if interim_ans > ans:
                ans = interim_ans
    return ans

if __name__ == '__main__':
    n, k = list(map(lambda x: int(x), input().split(" ")))
    inputs = get_while(n)
    print(solve(n, k, inputs))

Submission status: Wrong Answer

Solution code:

def match(x_origin, y_origin, expectations):
    match_count = 0
    for exp in expectations:
        x, y, c = exp
        color_change_x = (x - x_origin) % (K * 2) >= K
        color_change_y = (y - y_origin) % (K * 2) >= K
        actual_c = "B" if (color_change_x ^ color_change_y) else "W"

        if actual_c == c:
            match_count += 1

    return match_count


def check_all(expectations):
    for x_origin in xrange(K):
        for y_origin in xrange(K):
            yield match(x_origin, y_origin, expectations)


N, K = 0, 0
def solve():
    global N
    global K

    N, K = map(int, raw_input().split())

    expectations = list()
    for _ in xrange(N):
        x_s, y_s, c = raw_input().split()
        expectations.append((int(x_s), int(y_s), c))

    print max(check_all(expectations))


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
from operator import mul

# 整数Nを桁ごとのリストにする
# l = [int(x) for x in list(str(N))]

# リストliから重複を削除したリストli_uniqを作成
#li_uniq = []
#for i in li:
#    if x not in li_uniq:
#        li_uniq.append(x)

# 複数行のinput - list版
#list = [list(map(int, input().split())) for i in range(N)]
# 複数行のinput - dictionary版
# key = a, value = b
#for i in range(N):
#    a, b = map(int, input().split())
#    dict[a] = b


N, K = map(int, input().split())

req = []
x_min = y_min = 0
for i in range(N):
    x, y, c = input().split()
    if int(x) <= x_min: x_min = int(x)
    if int(y) <= y_min: y_min = int(y)
    req = req + [[int(x), int(y), c]]


#平行移動して第一象限へ
for i in range(N):
    req[i][0] = req[i][0] - x_min
    req[i][1] = req[i][1] - y_min

#市松模様の白の起点を(-i, -j)として総当り
n_max = 0
for i in range(K): #xを移動
    for j in range(i,K): #yを移動
        n = 0
        for k in range(N):
            if ((req[k][0] + i) // K) % 2 == 0:
                if ((req[k][1] + j) // K) % 2 == 0: #(x, y)はW
                    if req[k][2] == 'W': n += 1
                else:
                    if req[k][2] == 'B': n += 1
            else:
                if ((req[k][1] + j) // K) % 2 == 0: #(x, y)はB
                    if req[k][2] == 'B': n += 1
                else:
                    if req[k][2] == 'W': n += 1
        if n >= n_max or (N - n) >= n_max:
            n_max = max(n, N-n)

print(n_max)

Submission status: Wrong Answer

Solution code:
def det(x,K):
  return x % (2*K) in range(K)

def isblack(x,y,K):
  return (det(x,K) and det(y,K)) or (not (det(x,K) or det(y,K)))

def solve():
  raw = list(map(int,input().split(" ")))
  N = raw[0]
  K = raw[1]
  x=[]
  y=[]
  c=[]
  
  gain={}
  
  for i in range(N):
    raw = list(input().split(" "))
    x = int(raw[0])
    y = int(raw[1]) % (2*K)
    c = raw[2].strip('\r\n')
    if c == 'W':
      x = x + K
    x = x % (2*K)
    
    if (x,y) in gain:
      gain[(x,y)] = gain[(x,y)] + 1
    else:
      gain[(x,y)] = 1
  
  score = 0
  
  for i in range(K+1):
    for j in range(K+1):
      newscore = 0
      for keys in gain:
        k,l = keys
        if isblack(k-i,l-j,K):
          newscore = newscore + gain[(k,l)]
      score = max(score,newscore)
      
  return score

if __name__ == '__main__':
  
  ans = solve()
  print(ans, flush=True)

Submission status: Wrong Answer

Solution code:
import math

N,K = [int(i) for i in input().split()]
X = []
Y = []
C = []
for l in range(N):
    x,y,c = input().split()
    X.append(int(x))
    Y.append(int(y))
    if c == "W":
        C.append(1)
    else:
        C.append(0)

ans = 0
for dx in range(K):
    for dy in range(K):
        a = 0
        for i in range(N):
            if (math.floor((X[i] + dx) / K) % 2 + math.floor((Y[i] + dy) / K) % 2) % 2 == C[i]:
                a = a + 1
        ans = max(a, N-a)
        if ans == N:
            break
    if ans == N:
        break

print(ans)

Submission status: Wrong Answer

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

X=[]
Y=[]
C=[]
L=[]

W = [[] for i in range(K*2+1)]		#=> [[], [], []]
B = [[] for i in range(K*2+1)]		#=> [[], [], []]

for i in range(N):
	x, y, c = map(str, input().split())		# 5 7 2
	x=int(x)
	y=int(y)
	c = 1 if c=='W' else 0
	
	# Kで畳む
	if (x//K)%2==1: c=(c+1)%2
	x = x%K
	if (y//K)%2==1: c=(c+1)%2
	y = y%K

	X.append(x)
	Y.append(y)
	C.append(c)
	L.append( [x,y,c,1] )

#print(N, K)
#print(X)
#print(Y)
#print(C)
#print(L)

#同じのを消す(→wをカウントアップ)
L.sort(key=lambda x:x[2])
L.sort(key=lambda x:x[1])
L.sort(key=lambda x:x[0])
#print(L)

for i in range(N-1):
	j=i+1
	l = L[i]
	m = L[j]
#	print('l', l)
#	print('m', m)
	if l[0]==m[0] and l[1]==m[1] and l[2]==m[2]:
		m[3] += l[3]

		l[0] = -1
		l[1] = -1
		l[2] = -1
		l[3] = -1
		

M=[]
for i in range(N):
	if L[i][0] >= 0:
		M.append(L[i])

#	x, y, c, w = map(int, L[i])		# 5 7 2
#	print(x, y, c, w)
#	if x>=0:
#		M.append( [x,y,c,w] )


import copy
L = copy.deepcopy(M)
#print(L)
N=len(L)

# 0番目を、正方形の左下から始めて、他が条件を満たすか調べる
ok_max=0

x0, y0, c0, w0 = map(int, L[0])		# 5 7 2

for kx in range(K):
	for ky in range(K):

		ok=0
		for j in range(N):
			x, y, z, w = map(int, L[j])		# 5 7 2
			
			c=c0
			a = x-x0+kx
			if (a//K)%2 == 1: c=(c+1)%2
			
			b = y-y0+ky
			if (b//K)%2 == 1: c=(c+1)%2
			
			if c==z: ok += w

		ok_max = max(ok_max, ok)
		if ok_max==N:
			break

	if ok_max==N:
		break


print(ok_max)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, (input().split()))

lx, ly = [0] * K * 2, [0] * K * 2
for i in range(N):
    x, y, c = list(input().split())
    x, y = int(x), int(y)

    if c == 'B':
        lx[x % (2 * K)] += 1
        ly[y % (2 * K)] += 1
    else:
        lx[(x + K) % (2 * K)] += 1
        ly[(y + K) % (2 * K)] += 1

ans = 0
lx = lx * 2
ly = ly * 2

for i in range(K):
    sx = sum(lx[i:i + K])
    sy = sum(ly[i:i + K])
    ans = max(min(sx, sy), min(N - sx, N - sy), ans)

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
N, K = map(int, input().split())
x = [0] * N
y = [0] * N
c = [0] * N
for i in range(N):
    x[i], y[i], c[i] = input().split()
    x[i] = int(x[i])
    y[i] = int(y[i])
    c[i] = (0, 1)[c[i] == 'B']

ans = 0
sx = [set()] * K
sy = [set()] * K
for i in range(K):
    for j in range(N):
        if (((x[j] + i) // K) % 2) == c[j]:
            sx[i].add(j)
        if (((y[j] + i) // K) % 2) == c[j]:
            sy[i].add(j)

for i in range(K):
    for j in range(K):
        l = max(len(sx[i] - sy[j]), len(sy[j] - sx[i]))
        ans = max(ans, N - l)

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
#%%
def wOrB(strinp,a,b,k):
    [x,y,c] = strinp.split()
    x,y = int(x),int(y)
    x -= a
    y -= b
    if x%(2*k) <= k:
        if y%(2*k) <= k:
            col = 'W'
        else:
            col = 'B'
    else:
        if y%(2*k) <= k:
            col = 'B'
        else:
            col = 'W'
    if col == c:
        ans = 1
    else:
        ans = 0
    return ans

#%%
lst,lstinp = [],[]
n,k = map(int, input().split())
for i in range(n):
    lstinp.append(input())
for a in range(k):
    for b in range(k):
        count = 0
        for i in range(n):
            inp = lstinp[i]
            count += wOrB(inp,a,b,k)
        lst.append(count)
print(max(lst))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
b_x_list = []
b_y_list = []
w_x_list = []
w_y_list = []
order = []
for i in range(n):
    x_in, y_in, c_in = map(str, input().split())
    if c_in == "B":
        b_x_list.append(int(x_in))
        b_y_list.append(int(y_in))
    else:
        w_x_list.append(int(x_in))
        w_y_list.append(int(y_in))
    order.append([int(x_in), int(y_in), c_in])
"""
print(b_x_list)
print(b_y_list)
print(w_x_list)
print(w_y_list)
b_x = set(b_x_list)
b_y = set(b_y_list)
w_x = set(w_x_list)
w_y = set(w_y_list)
"""
num = 0
for i in range(k*2):
    for j in range(k*2):
        tmp_num = 0
        for l in range(len(w_x_list)):
            if i <= w_x_list[l] <= i+k and j <= w_y_list[l] <= j+k:
                tmp_num += 1
        if num < tmp_num + len(b_x_list):
            for l in range(len(b_x_list)):
                if (b_x_list[l] < i or i+k < b_x_list[l]) or (b_y_list[l] < j or j+k < b_y_list[l]):
                    tmp_num += 1
        num = max(num, tmp_num)
        if num == n:
            break

print(num)

Submission status: Wrong Answer

Solution code:
from pprint import pprint as pp
import collections
import math

n, k = map(int, input().split())
k2 = k * 2
result = { 'B': [[0] * k for i in range(k)],
          'W': [[0] * k for i in range(k)]}
# [x][y] -> sum if fill start x:y

for _ in range(n):
  x, y, c = input().split()
  x = int(x)
  y = int(y)
  modx = x % k2
  mody = y % k2
  for xi in range(k):
    for yi in range(k):
      result[c][(modx + xi) % k][(mody + yi) % k] += 1

pp(result)
print(max(max(ary) for ary in result))

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,k]=i2()
a=0
z=[[0 for i in range(2*k+1)]for j in range(2*k+1)]

for i in range(n):
 sg=input().split()
 s=[int(sg[0]),int(sg[1]),sg[2]]
 if ((s[0]//k+s[1]//k)%2==1 and s[2]=="B") or ((s[0]//k+s[1]//k)%2==0 and s[2]=="W"):
  z[s[1]%k+1][s[0]%k+1]+=1
  z[s[1]%k+k+1][s[0]%k+k+1]+=-1
  
  
 else:
  a+=1
  z[s[1]%k+1][s[0]%k+1]+=-1
  z[s[1]%k+k+1][s[0]%k+k+1]+=1
  
for i in range(2*k):
 for j in range(2*k+1):
  z[i+1][j]+=z[i][j]
for j in range(2*k):
 for i in range(2*k+1):
  z[i][j+1]+=z[i][j]
b=0
for i in range(2*k+1):
 for j in range(2*k+1):
  b=max(b,z[i][j])
print(a+b)

Submission status: Wrong Answer

Solution code:
N, K = list(map(int, input().split()))
x = list()
y = list()
c = list()

for i in range(N):
   XYC = list(input().split())
   x.append(int(XYC[0]))
   y.append(int(XYC[1]))
   c.append(XYC[2])
   
kibou_list = list()
for j in range(K): # x
   for k in range(K): # y
      kibou1 = 0
      kibou2 = 0
      for l in range(N):
         if ((x[l]+j)//K + (y[l]+k)//K)//2==0:
            if c[l] == c[0]:
               kibou1 = kibou1 + 1
            else:
               kibou2 = kibou2 + 1
         else:
            if c[l] != c[0]:
               kibou1 = kibou1 + 1
            else:
               kibou2 = kibou2 + 1
      kibou_list.append(kibou1)
      kibou_list.append(kibou2)

print(max(kibou_list))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
arrs = []
ans = 0
for i in range(n):
    arrs += [list(input().split())]
    arrs[i][:2] = list(map(int,arrs[i][:2]))

for arr in arrs:
    tmp = 0
    if ans <= n:
        for i in range(k):
            for j in range(k):
                arr[0] += i
                arr[1] += j
                x = int(arr[0]/k)%k
                y = int(arr[1]/k)%k
                if x == 0 and y == 0 and arr[2] == "B":
                    tmp += 1
                elif x == 1 and y == 1 and arr[2] == "B":
                    tmp += 1
                elif x == 1 and y == 0 and arr[2] == "W":
                    tmp += 1
                elif x == 0 and y == 1 and arr[2] == "W":
                    tmp += 1
                if tmp >= n:
                    ans = n
                    break
            if ans < tmp:
                ans = tmp
    else:
        pass
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import random
INF = 10**10
N,K = map(int,input().split())
x, y, c = [0]*N, [0]*N, [0]*N
minX = INF
minY = INF
maxX = -INF
maxY = -INF

for i in range(N):
	sx,sy,c[i] = map(str,input().split())
	x[i],y[i] = int(sx),int(sy)
	minX = min(minX, x[i])
	minY = min(minY, y[i])
	maxX = max(maxX, x[i])
	maxY = max(maxY, y[i])

# グループの最大幅
maxK = (maxX - minX + K) // K
if maxK % 2 == 0:
	maxK += 1
#for i in range(N):
#	print(x[i],y[i],c[i], file=sys.stderr)

res = 0
group = [0] * N
MAX_N = K
	
iter = 0
while iter < MAX_N:
	# 基準点
	bx = random.randint(minX - K, minX)
	by = random.randint(minY - K, minY)

	# 各点をこの基準点から算出して第何群に入るかを計算する
	for i in range(N):
		kx = (x[i] - bx) // K
		ky = (y[i] - by) // K
		group[i] = ky * maxK + kx

	for col in range(2):
		curr = 0
		if col == 0:
			# 奇数群が白、偶数群が黒
			for i in range(N):
				if group[i] % 2 == 0 and c[i] == 'B':
					curr += 1
				elif group[i] % 2 != 0 and c[i] == 'W':
					curr += 1
		else:
			# 奇数群が黒、偶数群が白
			for i in range(N):
				if group[i] % 2 != 0 and c[i] == 'B':
					curr += 1
				elif group[i] % 2 == 0 and c[i] == 'W':
					curr += 1
		res = max(res, curr)
		iter += 1

print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np
from math import ceil
n, k = map(int, input().split())
maxx = 0
lists = []
for i in range(n):
    a = input().split()
    lists.append([int(a[0])/k, int(a[1])/k, 0 if a[2] == "W" else 1])
lists = np.array(lists)
for i in range(-ceil((k+1)/4),ceil((k+1)/4)):
    for j in range(-ceil((k+1)/4),ceil((k+1)/4)):
        a = lists + [i, j, 0]
        l = a[((a[:,0]+i) // k + (a[:,1]+j) // k) % 2 != a[:,2]]
        maxx = max(maxx, max(len(l), n - len(l)))
        print(l)
print(maxx)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = list(map(int, input().split()))
x = np.zeros(N, dtype=np.uint32)
y = np.zeros(N, dtype=np.uint32)
c = np.zeros(N, dtype=np.bool)

for i in range(N):
    s = input().split()
    x[i], y[i] = list(map(int, s[0:2]))
    c[i] = (s[2]=="W")

x_true = np.zeros(N, dtype=np.uint32)
y_true = np.zeros(N, dtype=np.uint32)
for i in range(N):
    if (x[i] // K) % 2 == 0:
        x_true[i] = int(x[i] % K)
        y_true[i] = int((y[i] + c[i] * K) % (2*K))
    else:
        x_true[i] = int(x[i] % K)
        y_true[i] = int((y[i] + c[i] * K + K) % (2*K))
counter = np.zeros((K, 2*K), dtype=np.uint32)
for i in range(len(y_true)):
    counter[x_true[i], y_true[i]] += 1

sum_counter = np.zeros((K, 2*K), dtype=np.uint32)
s = np.sum(counter)
for x_k in range(K):
    for y_k in range(2*K):
        if y_k < K:
            sum_counter[x_k, y_k] = counter[x_k:K, y_k:y_k+K].sum() + counter[0:x_k,0:y_k].sum() + counter[0:x_k,y_k+K:2*K].sum()
        else:
            sum_counter[x_k, y_k] = counter[0:x_k, y_k-K:y_k].sum() + counter[x_k:K, 0:y_k].sum() + counter[x_k:K, y_k+K:2*K].sum()

print(np.max(sum_counter.ravel()))

Submission status: Wrong Answer

Solution code:
import math

tmp = input().split()
N = int(tmp[0])
K = int(tmp[1])


w=0
b=0
for i in range(N):
    tmp = input().split()
    x = int(tmp[0])
    y = int(tmp[1])
    c = tmp[2]
    if c == "W":
        x = x + K
    x = x % (2 * K)
    y = y % (2 * K)
    if x >= K and y >= K:
        x = x - K
        y = y - K
    elif x < K and y >= K:
        x = x + K
        y = y - K

    if y >=K:
        w+=1
    else:
        b+=1
    
if w > b:
    print(w)
else:
    print(b)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from math import factorial, ceil, sqrt, atan2, log
from itertools import *
import string
import copy
import random
import bisect
from decimal import *
def id_generator(size=20, chars=string.digits):
    return ''.join(random.choice(chars) for _ in range(size))
 
def mp():
    return map(int,str(raw_input()).split())

n,k=mp()
b=[]
w=[]
for i in range(n):
	l=str(raw_input()).split()
	x,y,c=int(l[0]),int(l[1]),l[2]
	x,y=x%(2*k),y%(2*k)
	if c=='b':
		b+=[[x,y]]
	else:
		w+=[[x,y]]

#print b,w

pre1=[[0 for i in range(2*k)] for j in range(2*k)]
l1=[[0 for i in range(2*k)] for j in range(2*k)]
pre2=[[0 for i in range(2*k)] for j in range(2*k)]
l2=[[0 for i in range(2*k)] for j in range(2*k)]

for i in b:
	l1[i[0]][i[1]]+=1

for i in w:
	l2[i[0]][i[1]]+=1

pre1[0][0]=l1[0][0]
pre2[0][0]=l2[0][0]
for i in range(1,2*k):
	pre1[i][0]=pre1[i-1][0]+l1[i][0]
	pre1[0][i]=pre1[0][i-1]+l1[0][i]
	pre2[i][0]=pre2[i-1][0]+l2[i][0]
	pre2[0][i]=pre2[0][i-1]+l2[0][i]

for i in range(1,2*k):
	for j in range(1,2*k):
		pre1[i][j]=(-pre1[i-1][j-1]+pre1[i-1][j]+pre1[i][j-1]+l1[i][j])
		pre2[i][j]=(-pre2[i-1][j-1]+pre2[i-1][j]+pre2[i][j-1]+l2[i][j])
		
ans=0
ok=k*2-1

for i in range(1,2*k):
	for j in range(1,2*k):
		val=0
		if i<k:
			if j<k:
				val+=pre1[i+k][j+k]-pre1[i][j+k]-pre1[i+k][j]+pre1[i][j]

				val+=pre1[ok][ok]-pre1[i+k][ok]-pre1[ok][j+k]+pre1[i][j]

				val+=pre2[i+k][ok]-pre2[i+k][j+k]-pre2[i][ok]+pre2[i][j+k]

				val+=pre2[ok][j+k]-pre2[i+k][j+k]-pre2[ok][j]+pre2[i+k][j]

			else:
				j-=k
				val+=pre2[i+k][j+k]-pre2[i][j+k]-pre2[i+k][j]+pre2[i][j]

				val+=pre2[ok][ok]-pre2[i+k][ok]-pre2[ok][j+k]+pre2[i][j]

				val+=pre1[i+k][ok]-pre1[i+k][j+k]-pre1[i][ok]+pre1[i][j+k]

				val+=pre1[ok][j+k]-pre1[i+k][j+k]-pre1[ok][j]+pre1[i+k][j]
		else:
			if j<k:
				i-=k
				val+=pre2[i+k][j+k]-pre2[i][j+k]-pre2[i+k][j]+pre2[i][j]

				val+=pre2[ok][ok]-pre2[i+k][ok]-pre2[ok][j+k]+pre2[i][j]

				val+=pre1[i+k][ok]-pre1[i+k][j+k]-pre1[i][ok]+pre1[i][j+k]

				val+=pre1[ok][j+k]-pre1[i+k][j+k]-pre1[ok][j]+pre1[i+k][j]
			else:
				i-=k

				j-=k

				val+=pre1[i+k][j+k]-pre1[i][j+k]-pre1[i+k][j]+pre1[i][j]

				val+=pre1[ok][ok]-pre1[i+k][ok]-pre1[ok][j+k]+pre1[i][j]

				val+=pre2[i+k][ok]-pre2[i+k][j+k]-pre2[i][ok]+pre2[i][j+k]

				val+=pre2[ok][j+k]-pre2[i+k][j+k]-pre2[ok][j]+pre2[i+k][j]

		ans=max(ans,val)


for i in range(k):
	val=0
	val+=pre1[i+k][k-1]-pre1[i][k-1]
	val+=pre1[ok][ok]-pre1[i+k][ok]-pre1[ok][k-1]+pre1[i+k][k-1]+pre1[i][ok]-pre1[i][k-1]
	val+=pre2[i][k-1]+pre2[i+k][ok]-pre2[i][ok]-pre2[i+k][k-1]+pre2[i][k-1]+pre2[ok][k-1]-pre2[i+k][k-1]
	ans=max(ans,val)




ans=max(pre1[ok][ok]-pre1[ok][k-1]-pre1[k-1][ok]+2*pre1[k-1][k-1]+pre2[ok][k-1]+pre2[k-1][ok]-2*pre2[k-1][k-1],ans)
pre1,pre2=pre2,pre1
ans=max(pre1[ok][ok]-pre1[ok][k-1]-pre1[k-1][ok]+2*pre1[k-1][k-1]+pre2[ok][k-1]+pre2[k-1][ok]-2*pre2[k-1][k-1],ans)
for i in range(k):
	val=0
	val+=pre1[i+k][k-1]-pre1[i][k-1]
	val+=pre1[ok][ok]-pre1[i+k][ok]-pre1[ok][k-1]+pre1[i+k][k-1]+pre1[i][ok]-pre1[i][k-1]
	val+=pre2[i][k-1]+pre2[i+k][ok]-pre2[i][ok]-pre2[i+k][k-1]+pre2[i][k-1]+pre2[ok][k-1]-pre2[i+k][k-1]
	ans=max(ans,val)


print ans



'''
n=input()
l=[]
x1,y1=0,0
flag=1
t1=0
for i in range(n):
	t,x,y=mp()
	t-=t1
	if (abs(x-x1)+abs(y-y1))<=t:
		if (abs(x-x1)+abs(y-y1))%2!=t%2:
			flag=0
	else:
		flag=0
	x1,y1=x,y
	t1=t

if flag:
	print 'Yes'
else:
	print 'No'
'''

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools

def isBlack(K, shift, pos):
    x = shift[0] + pos[0]
    y = shift[1] + pos[1]

    l = int(x/K) + int(y/K)

    return l % 2 == 0

N, K = tuple(map(int, input().split(' ')))

desires = []

for i in range(N):
    inp = input().split(" ")
    inp[0] = int(inp[0])
    inp[1] = int(inp[1])
    desires.append(inp)

maxim = 0

for s1 in range(N):
    count_1 = 0
    count_2 = 0

    for s2 in range(N):
        shift = (s1, s2)

        for i in range(N):
            isB = isBlack(K, shift, desires[i][:2])

            if isB and desires[i][2] == 'B':
                count_1 += 1
            elif (not isB) and desires[i][2] == 'W':
                count_1 += 1

            if isB and desires[i][2] == 'W':
                count_2 += 1
            elif (not isB) and desires[i][2] == 'B':
                count_2 += 1

            if count_1 + N - i - 1 < maxim and count_2 + N - i - 1 < maxim:
                break

        if maxim < count_1:
            maxim = count_1
        if maxim < count_2:
            maxim = count_2

        if maxim == N:
            print(maxim)
            sys.exit()

print(maxim)

Submission status: Wrong Answer

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

N, K = map(int, input().split())

xs = [{'ok':0,'ng':0} for i in range(K)]
ys = [{'ok':0,'ng':0} for i in range(K)]
zs = [[{'ok':0,'ng':0} for i in range(K)] for j in range(K)]
ok = 0
for i in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    x_bit = (x//K) % 2
    y_bit = (y//K) % 2
    x_mod = x%K
    y_mod = y%K
    color = ''
    flg = ''
    if (x_bit+y_bit) % 2 == 0:
        if c == 'W':
            ok += 1
            xs[x_mod]['ok'] += 1
            ys[y_mod]['ok'] += 1
            color = 'W'
            flg = 'ok'
        else:
            xs[x_mod]['ng'] += 1
            ys[y_mod]['ng'] += 1
            color = 'W'
            flg = 'ng'
    else:
        if c == 'B':
            ok += 1
            xs[x_mod]['ok'] += 1
            ys[y_mod]['ok'] += 1
            color = 'B'
            flg = 'ok'
        else:
            xs[x_mod]['ng'] += 1
            ys[y_mod]['ng'] += 1
            color = 'B'
            flg = 'ng'
    zs[y_mod][x_mod][flg] += 1


ans = [[0 for i in range(K)] for j in range(K)]

tmp = ok
for i in range(1,K):
    ans[0][i] = tmp - xs[i-1]['ok'] + xs[i-1]['ng']


# for j in range(1,K):
#     for i in range(1,K):
#         ans[j][i] = ans[j-1][i] - ys[j]['ok'] + xs[j]['ng']


tmp = ok
for j in range(1,K):
    ans[j][0] = tmp - ys[j-1]['ok'] + ys[j-1]['ng']

for i in range(1,K):
    for j in range(1,K):
        ans[i][j] = ans[i-1][j-1] - xs[i-1]['ok'] + xs[i-1]['ng']- ys[j-1]['ok'] + ys[j-1]['ng'] - (-zs[j-1][i-1]['ok']+zs[j-1][i-1]['ng'])


print(max(max(ans)))

Submission status: Wrong Answer

Solution code:
from itertools import product

n,k=map(int,input().split())

ans=0
k2=2*k

b=[[0 for i in range(k2)] for j in range(k2)]
w=[[0 for i in range(k2)] for j in range(k2)]
for i in range(n):
    x,y,c=input().split()
    if(c=='B'):
        b[int(x)%k2][int(y)%k2]+=1
    else:
        w[int(x)%k2][int(y)%k2]+=1

for i_x,i_y in product(range(k),repeat=2):
    ans+=max(b[i_x][i_y]+b[i_x+k][i_y+k]+w[i_x+k][i_y]+w[i_x][i_y+k],w[i_x][i_y]+w[i_x+k][i_y+k]+b[i_x+k][i_y]+b[i_x][i_y+k])

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from math import ceil
n, k = map(int, input().split())
maxx = 0
lists = []
for i in range(n):
    a = input().split()
    lists.append([int(a[0])/k, int(a[1])/k, 0 if a[2] == "W" else 1])
lists = np.array(lists)
for i in range(-ceil((k+1)/4),ceil((k+1)/4)):
    for j in range(-ceil((k+1)/4),ceil((k+1)/4)):
        a = lists + [i, j, 0]
        l = ((a[:,0]+i) // k + (a[:,1]+j) // k) % 2 != a[:,2]
        maxx = max(maxx, max(np.sum(l), n - np.sum(l)))
        print(l)
print(maxx)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, K = list(map(int, input().split()))
x = []
y = []
c = []
for i in range(N):
    xi, yi, ci = list(map(str, input().split()))
    x.append(int(xi))
    y.append(int(yi))
    c.append(ci)


maxFilled = 0
# Bを基準に考える
for i in range(min(K+1, max(x))):
    for j in range(min(K+1, max(y))):
        cnt = 0
        for idx in range(len(c)):
            h = (x[idx]-i) // K # 水平方向に何番目(0-indexed)のブロックか?
            v = (y[idx]-j) // K # 垂直方向に何番目のブロックか?
            if (v % 2 == 1 and h % 2 == 0 and c[idx] == 'W') or \
               (v % 2 == 0 and h % 2 == 0 and c[idx] == 'B') or \
               (v % 2 == 0 and h % 2 == 1 and c[idx] == 'W') or \
               (v % 2 == 1 and h % 2 == 1 and c[idx] == 'B'):
                cnt += 1
        maxFilled = max(maxFilled, cnt)


print(maxFilled)

Submission status: Wrong Answer

Solution code:
n, k = map(int, raw_input().split())
mp = [[-1] * k for _ in xrange(k)]
d = []
m = {'B': 0, 'W': 1}
for _ in xrange(n):
    x, y, c = raw_input().split()
    x, y = int(x), int(y)
    c = abs(m[c] - (((x / k) & 1) + ((y / k) & 1)) & 1)
    d.append([x % k, y % k, c])
ans = 0
for cx in xrange(k):
    for cy in xrange(k):
        cnt = 0
        for x, y, c in d:
            if (x - cx) * (y - cy) < 0:
                if not c:
                    cnt += 1
            else:
                if c:
                    cnt += 1
        ans = max(ans, cnt, n - cnt)
print ans

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,k]=i2()
a=0
z=[[0 for i in range(2*k+1)]for j in range(2*k+1)]

for i in range(n):
 sg=input().split()
 s=[int(sg[0]),int(sg[1]),sg[2]]
 if ((s[0]//k+s[1]//k)%2==1 and s[2]=="B") or ((s[0]//k+s[1]//k)%2==0 and s[2]=="W"):
  z[0][s[0]%k+1]+=1
  z[0][s[0]%k+k+1]+=-1
  z[s[1]%k+1][0]+=1
  z[s[1]%k+k+1][0]+=-1
  
 else:
  a+=1
  z[0][s[0]%k+1]+=-1
  z[0][s[0]%k+k+1]+=1
  z[s[1]%k+1][0]+=-1
  z[s[1]%k+k+1][0]+=1
for i in range(2*k):
 z[0][i+1]+=z[0][i]
for i in range(2*k):
 z[i+1][0]+=z[i][0]
b=0
for i in range(2*k+1):
 for j in range(2*k+1):
  b=max(b,z[i][j])
print(a+b)

Submission status: Wrong Answer

Solution code:
from pprint import pprint as pp
import collections
import math

n, k = map(int, input().split())
k2 = k * 2
result = [[0] * k2 for i in range(k2)]
# [x][y] -> sum if fill start x:y

for _ in range(n):
  x, y, c = input().split()
  x = int(x)
  y = int(y)
  if c == 'W':
    x += k
    y += k
  modx = x % k2
  mody = y % k2
  for xi in range(k):
    xi = (modx + xi) % k2
    for yi in range(k):
      result[xi][(mody + yi) % k2] += 1
  for xi in range(k):
    xi = (modx + xi + k) % k2
    for yi in range(k):
      result[xi][(mody + yi + k) % k2] += 1

print(max(max(ary) for ary in result))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, K = list(map(int, input().split()))
x = []
y = []
c = []
for i in range(N):
    xi, yi, ci = list(map(str, input().split()))
    x.append(int(xi))
    y.append(int(yi))
    c.append(ci)


maxFilled = 0
# Bを基準に考える
for i in range(max(x)+1):
    for j in range(max(y)+1):
        cnt = 0
        for idx in range(len(c)):
            h = (x[idx]-i) // K # 水平方向に何番目(0-indexed)のブロックか?
            v = (y[idx]-j) // K # 垂直方向に何番目のブロックか?
            if (v % 2 == 1 and h % 2 == 0 and c[idx] == 'W') or \
               (v % 2 == 0 and h % 2 == 0 and c[idx] == 'B') or \
               (v % 2 == 0 and h % 2 == 1 and c[idx] == 'W') or \
               (v % 2 == 1 and h % 2 == 1 and c[idx] == 'B'):
                cnt += 1
        maxFilled = max(maxFilled, cnt)


print(maxFilled)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, (input().split()))

lx, ly = [0] * K * 2, [0] * K * 2
for i in range(N):
    x, y, c = list(input().split())
    x, y = int(x), int(y)

    if c == 'B':
        lx[x % (2 * K)] += 1
        ly[y % (2 * K)] += 1
    else:
        lx[(x + K) % (2 * K)] += 1
        ly[(y + K) % (2 * K)] += 1

ansx, ansy = 0, 0
lx = lx * 2
ly = ly * 2

for i in range(2 * K):
    sx, sy = sum(lx[i:i + K]), sum(ly[i:i + K])
    ansx = max(ansx, sx, N - sx)
    ansy = max(ansy, sy, N - sy)

print(min(ansx, ansy))

Submission status: Wrong Answer

Solution code:
import numpy as np
from math import ceil
n, k = map(int, input().split())
maxx = 0
lists = []
for i in range(n):
    a = input().split()
    lists.append([int(a[0]), int(a[1]), 0 if a[2] == "W" else 1])
lists = np.array(lists)
for i in range(-ceil((k+1)/4),ceil((k+1)/4)):
    for j in range(-ceil((k+1)/4),ceil((k+1)/4)):
        l = np.sum((lists[:,0]+i // k + lists[:,1]+j // k) % 2 != lists[:,2])
        maxx = max(maxx, max(l, n - l))
print(maxx)