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: Time Limit Exceeded

Solution code:
def main():
    from itertools import accumulate as ac
    n,k=map(int,input().split())
    kk=2*k
    xyc=[input().split() for _ in [0]*n]
    b=[[0]*(k+1) for _ in [0]*(kk+1)]
    for x,y,c in xyc:
        if c=="B":
            if int(y)%kk<k:
                b[int(x)%kk+1][int(y)%k+1]+=1
            else:
                b[(int(x)+k)%kk+1][int(y)%k+1]+=1
        else:
            if int(y)%kk<k:
                b[(int(x)+k)%kk+1][int(y)%k+1]+=1
            else:
                b[int(x)%kk+1][int(y)%k+1]+=1
    b=[list(ac(i)) for i in b]
    for i in range(1,kk+1):
        for j in range(k+1):
            b[i][j]+=b[i-1][j]
    ans=0
    for i in range(kk):
        if i==0:
            a_t=((i,i+k,0),(i+k,kk,1))
        elif i<k:
            a_t=((0,i,-1),(i,i+k,0),(i+k,kk,1))
        elif i==k:
            a_t=((0,i,-1),(i,kk,0))
        else:
            a_t=((0,i-k,-2),(i-k,i,-1),(i,kk,0))
        for j in range(k):
            if j==0:
                b_t=((0,k,0),)
            else:
                b_t=((0,j,-1),(j,k,0))
            black=[]
            for i,j,l in a_t:
                for x,y,z in b_t:
                    if (l+z)%2==0:
                        black.append((i,x,j,y))
            ret=0
            for tx1,ty1,tx2,ty2 in black:
                ret+=b[tx1][ty1]+b[tx2][ty2]-b[tx1][ty2]-b[tx2][ty1]
            ans=max(ans,ret)
    print(ans)
main()

Submission status: Time Limit Exceeded

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

Map = [[[0]*K for i in range(K)] for j in range(2)]
for i in range(N):
  x, y, c = input().split()
  x, y = int(x), int(y)
  if c == 'B':
    c = 0
  else:
    c = 1
  nx, ny = x//K, y//K
  if (nx + ny) % 2:
    c = 1 - c
  x %= K
  y %= K
  Map[c][x][y] += 1

def get_v(c, x, y):
  global Map
  if x < 0 or y < 0:
    return 0
  else:
    return Map[c][x][y]

for c in range(2):
  for x in range(K):
    for y in range(K):
      Map[c][x][y] += get_v(c, x-1, y) + get_v(c, x, y-1) - get_v(c, x-1, y-1)

ans = 0
for x in range(K+1):
  for y in range(K+1):
    b2 = get_v(0, x-1, K-1) + get_v(0, K-1, y-1) - 2*get_v(0, x-1, y-1)
    w1 = get_v(1, x-1, K-1) + get_v(1, K-1, y-1) - 2*get_v(1, x-1, y-1)
    b1 = Map[0][K-1][K-1] - b2
    w2 = Map[1][K-1][K-1] - w1
    ans = max(ans, b1+w1, b2+w2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def double_accumulate(a):
    h = len(a)
    w = len(a[0])
    b = [[0]*(w+1) for i in range(h+1)]
    b[1][1] = a[0][0]
    for i in range(h):
        for j in range(w):
            b[i+1][j+1] = b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]
    return tuple(tuple(x) for x in b)


def double_sum(b,p,q):
    return b[q[0]+1][q[1]+1]-b[q[0]+1][p[1]]-b[p[0]][q[1]+1]+b[p[0]][p[1]]


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

kk = k*2

black = [[0]*kk for i in range(kk)]
white = [[0]*kk for i in range(kk)]

for i in range(n):
    x,y,c = input().split()
    x = int(x)%kk
    y = int(y)%kk
    if c == 'B':
        black[x][y]+=1
    else:
        white[x][y]+=1

black = tuple(tuple(black[i%kk]*2) for i in range(kk*2))
white = tuple(tuple(white[i%kk]*2) for i in range(kk*2))

B = double_accumulate(black)
W = double_accumulate(white)

ans = 0
for i in range(kk):
    for j in range(kk):
        b = double_sum(B,[i,j],[i+k-1,j+k-1])\
            + double_sum(B,[i+k,j+k],[i+kk-1,j+kk-1])
        w = double_sum(W,[i,j+k],[i+k-1,j+kk-1])\
            + double_sum(W,[i+k,j],[i+kk-1,j+k-1])
        ans = max(ans,b+w)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def double_accumulate(a):
    h = len(a)
    w = len(a[0])
    b = [[0]*(w+1) for i in range(h+1)]
    b[1][1] = a[0][0]
    for i in range(h):
        for j in range(w):
            b[i+1][j+1] = b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]
    return tuple(tuple(x) for x in b)

def double_sum(b,p,q):
    y1,x1 = p
    y2,x2 = q
    if y1>y2 or x1>x2:
        return 0
    else:
        return b[y2+1][x2+1]-b[y2+1][x1]-b[y1][x2+1]+b[y1][x1]


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

kk = k*2

black = [[0]*kk for i in range(kk)]
white = [[0]*kk for i in range(kk)]

for i in range(n):
    x,y,c = input().split()
    x = int(x)%kk
    y = int(y)%kk
    if c == 'B':
        black[x][y]+=1
    else:
        white[x][y]+=1

black = tuple(tuple(black[i%kk]*2) for i in range(kk*2))
white = tuple(tuple(white[i%kk]*2) for i in range(kk*2))

B = double_accumulate(black)
W = double_accumulate(white)

ans = 0
for i in range(kk):
    for j in range(kk):
        b = double_sum(B,[i,j],[i+k-1,j+k-1])\
            + double_sum(B,[i+k,j+k],[i+kk-1,j+kk-1])
        w = double_sum(W,[i,j+k],[i+k-1,j+kk-1])\
            + double_sum(W,[i+k,j],[i+kk-1,j+k-1])
        ans = max(ans,b+w)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

INF = float("inf")


class Acc2D:
    def __init__(self, grid):
        self.h, self.w = len(grid), len(grid[0])
        self.acc2D = self._build(self.h, self.w, grid)

    def _build(self, h, w, grid):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r][c + 1] + ret[r + 1][c] - ret[r][c] + grid[r][c]
        return ret

    def get(self, r1, r2, c1, c2):
        if r1 < 0:
            r1 = 0
        if r2 >= self.h:
            r2 = self.h
        if c1 < 0:
            c1 = 0
        if c2 >= self.w:
            c2 = self.w
        cnt = self.acc2D
        return cnt[r2][c2] - cnt[r1][c2] - cnt[r2][c1] + cnt[r1][c1]


def main():
    n, k = map(int, input().split())
    g = [[0] * (2 * k) for _ in range(2 * k)]
    for _ in range(n):
        x, y, c = input().split()
        x = int(x) % (2 * k)
        y = int(y) % (2 * k)
        if c == 'B':
            y = (y + k) % (2 * k)
        g[y][x] += 1
    acc2d = Acc2D(g)
    ans = 0
    for r in range(k):
        for c in range(k):
            tmp = acc2d.get(0, r, 0, c)
            tmp += acc2d.get(0, r, c + k, c + k * 2)
            tmp += acc2d.get(r, r + k, c, c + k)
            tmp += acc2d.get(r + k, r + k * 2, 0, c)
            tmp += acc2d.get(r + k, r + k * 2, c + k, c + k * 2)
            ans = max(ans, tmp, n - tmp)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class Acc2D:
    def __init__(self, a, K):
        h, w = len(a), len(a[0])
        self.acc2D = self._build(h, w, a)
        self.K = K

    def _build(self, h, w, a):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r][c + 1] + ret[r + 1][c] - ret[r][c] + a[r][c]
                # 末項は必要に応じて改変すること
        return ret

    def get(self, r1, r2, c1, c2):
        # [r1,r2), [c1,c2) : 0-indexed
        if r1 < 0: r1 = 0
        if r2 >= self.K * 2: r2 = self.K * 2
        if c1 < 0: c1 = 0
        if c2 >= self.K * 2: c2 = self.K * 2
        acc2D = self.acc2D
        return acc2D[r2][c2] - acc2D[r1][c2] - acc2D[r2][c1] + acc2D[r1][c1]


def main():
    import sys
    input = sys.stdin.readline

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

    g = [[0] * (K * 2) for _ in range(K * 2)]
    for _ in range(N):
        x, y, c = input().split()
        x = int(x) % (K * 2)
        y = (int(y) - (K if c == 'B' else 0)) % (K * 2)
        g[x][y] += 1  # White

    acc2d = Acc2D(g, K)
    ans = -1
    for r in range(K):
        for c in range(K):
            t = acc2d.get(0, r, 0, c)
            t += acc2d.get(0, r, c + K, c + K * 2)
            t += acc2d.get(r, r + K, c, c + K)
            t += acc2d.get(r + K, r + K * 2, 0, c)
            t += acc2d.get(r + K, r + K * 2, c + K, c + K * 2)
            ans = max(ans, t, N - t)
    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()

Submission status: Time Limit Exceeded

Solution code:
import sys

#縦k、横kのマスに移動させて考える
n, k = map(int, sys.stdin.readline().strip().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = sys.stdin.readline().strip().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

graph = [[0 for _ in range(k)] for __ in range(k)]

#累積和
#lx + lmx = n
lx = len(x)
for i in range(lx):
    for j in range(x[i], k):
        graph[j][y[i]] += 1
    for j in range(x[i]):
        graph[j][0] += 1
        graph[j][y[i]] -= 1

lmx = len(mx)
for i in range(lmx):
    for j in range(mx[i], k):
        graph[j][my[i]] -= 1
    for j in range(mx[i]):
        graph[j][0] -= 1
        graph[j][my[i]] += 1

for i in range(k):
    for j in range(k-1):
        graph[i][j+1] += graph[i][j]

#最大値、最小値を取得
big = max([max(i) for i in graph]) + lmx
small = min([min(i) for i in graph]) - lx

if big + small >= 0:
    print(big)
else:
    print(-small)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline().strip()

#縦k、横kのマスに移動させて考える
n, k = map(int, input().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = input().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

graph = [[0 for _ in range(k)] for __ in range(k)]

#累積和
#lx + lmx = n
lx = len(x)
for i in range(lx):
    for j in range(x[i], k):
        graph[j][y[i]] += 1
    for j in range(x[i]):
        graph[j][0] += 1
        graph[j][y[i]] -= 1

lmx = len(mx)
for i in range(lmx):
    for j in range(mx[i], k):
        graph[j][my[i]] -= 1
    for j in range(mx[i]):
        graph[j][0] -= 1
        graph[j][my[i]] += 1

for i in range(k):
    for j in range(k-1):
        graph[i][j+1] += graph[i][j]

#最大値、最小値を取得
big = max([max(i) for i in graph]) + lmx
small = min([min(i) for i in graph]) - lx

if big + small >= 0:
    print(big)
else:
    print(-small)

Submission status: Time Limit Exceeded

Solution code:
import sys

#縦k、横kのマスに移動させて考える
n, k = map(int, sys.stdin.readline().strip().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = input().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

graph = [[0 for _ in range(k)] for __ in range(k)]

#累積和
#lx + lmx = n
lx = len(x)
for i in range(lx):
    for j in range(x[i], k):
        graph[j][y[i]] += 1
    for j in range(x[i]):
        graph[j][0] += 1
        graph[j][y[i]] -= 1

lmx = len(mx)
for i in range(lmx):
    for j in range(mx[i], k):
        graph[j][my[i]] -= 1
    for j in range(mx[i]):
        graph[j][0] -= 1
        graph[j][my[i]] += 1

for i in range(k):
    for j in range(k-1):
        graph[i][j+1] += graph[i][j]

#最大値、最小値を取得
big = max([max(i) for i in graph]) + lmx
small = min([min(i) for i in graph]) - lx

if big + small >= 0:
    print(big)
else:
    print(-small)

Submission status: Time Limit Exceeded

Solution code:
#縦k、横kのマスに移動させて考える
n, k = map(int, input().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = input().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

graph = [[0 for _ in range(k)] for __ in range(k)]

#累積和
#lx + lmx = n
lx = len(x)
for i in range(lx):
    for j in range(x[i], k):
        graph[j][y[i]] += 1
    for j in range(x[i]):
        graph[j][0] += 1
        graph[j][y[i]] -= 1

lmx = len(mx)
for i in range(lmx):
    for j in range(mx[i], k):
        graph[j][my[i]] -= 1
    for j in range(mx[i]):
        graph[j][0] -= 1
        graph[j][my[i]] += 1

for i in range(k):
    for j in range(k-1):
        graph[i][j+1] += graph[i][j]

#最大値、最小値を取得
big = max([max(i) for i in graph]) + lmx
small = min([min(i) for i in graph]) - lx

if big + small >= 0:
    print(big)
else:
    print(-small)

Submission status: Time Limit Exceeded

Solution code:
# D - Checker

import numpy as np

N, K = map(int, input().split())
g = np.zeros((K,K), np.int64) # PDF解説通り2K*2K範囲でやると市松模様の処理が大変なのでK*Kの範囲で計算

for _ in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    tmp = (x//K + y//K) % 2
    x %= K
    y %= K
    if (tmp == 0 and c == "B") or (tmp == 1 and c == "W"):
        g[x][y] += 1
    else:
        g[x][y] -= 1 # 白希望の点を-1で記録する

np.cumsum(g, axis=0, out=g)
np.cumsum(g, axis=1, out=g)

# [i,j]を黒範囲の左下の点とする。[0,i] * [0,j] の範囲または[i+1,K-1] * [j+1,K-1]の範囲にある黒希望点の個数を足し、白希望の点の個数を引く
# 上記範囲外にある白希望の点の個数を足し、黒希望の点の個数を引く
ans = 0
for i in range(K):
    for j in range(K):
        n_satisfied = g[-1][-1] -2*(g[-1][j] + g[i][-1]) + 4*g[i][j]
        ans = max(ans, (N + n_satisfied)//2, (N - n_satisfied)//2) # ((希望通りの点 + 希望通りでない点) + (希望通りの点 - 希望通りでない点))//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

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

K2=K*2

groupW=np.zeros((K2,K2))
groupB=np.zeros((K2,K2))
#group=np.zeros((K2,K2))

one=np.ones((1,K))
#posneg=np.hstack([one, -one])
#negpos=np.hstack([-one,one])
#posnegK=np.vstack([posneg]*K)
#negposK=np.vstack([negpos]*K)
#mask=np.vstack([posnegK, negposK])

zero=np.zeros((1,K))
poszero=np.hstack([one, zero])
zeropos=np.hstack([zero,one])
poszeroK=np.vstack([poszero]*K)
zeroposK=np.vstack([zeropos]*K)
mask_zp=np.vstack([poszeroK, zeroposK])


zeroneg=np.hstack([zero, -one])
negzero=np.hstack([-one,zero])
zeronegK=np.vstack([zeroneg]*K)
negzeroK=np.vstack([negzero]*K)
mask_nz=np.vstack([zeronegK, negzeroK])


for i in range(N):
    (x,y,c)=input().split()
    x=int(x) % K2
    y=int(y) % K2
    if c=='W':
        groupW[x][y]+=1
        #group[x][y]+=1
    else:
        groupB[x][y]-=1
        #group[x][y]-=1

#FG=np.fft.fft2(group)
FW=np.fft.fft2(groupW)
FB=np.fft.fft2(groupB)

#FM=np.fft.fft2(mask)

FM_zp=np.fft.fft2(mask_zp)
FM_nz=np.fft.fft2(mask_nz)

#FH=FG*FM
#H=np.real(np.fft.ifft2(FH))

FH_zp=FW*FM_zp
FH_nz=FB*FM_nz
H_zp=np.real(np.fft.ifft2(FH_zp))
H_nz=np.real(np.fft.ifft2(FH_nz))
H_all=H_zp+H_nz

(x0,y0)=np.unravel_index(np.argmax(H_all), H_all.shape)
#x1=x0-K
#y1=y0-K
print(int(H_all[x0,y0]+0.5))

Submission status: Time Limit Exceeded

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

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
mod = K * 2
XY = []
MAX = K*6 + 7
acc = list2d(MAX, MAX, 0)
for i in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    x %= mod
    y %= mod
    if c == 'B':
        x += K
    for a1 in range(3):
        for a2 in range(3):
            for b in [0, K]:
                if c == 'B':
                    b = -b
                x1 = x + a1 * mod + b
                y1 = y + a2 * mod + b
                x2 = x1 + K
                y2 = y1 + K
                x1 = max(min(x1, MAX-1), 0)
                y1 = max(min(y1, MAX-1), 0)
                x2 = max(min(x2, MAX-1), 0)
                y2 = max(min(y2, MAX-1), 0)
                acc[x1][y1] += 1
                acc[x2][y2] += 1
                acc[x1][y2] -= 1
                acc[x2][y1] -= 1

for i in range(MAX):
    acc[i] = list(accumulate(acc[i]))
for j in range(MAX):
    for i in range(MAX-1):
        acc[i+1][j] += acc[i][j]
mx = 0
for j in range(K*2, K*4):
    for i in range(K*2, K*4):
        mx = max(mx, acc[i][j])
print(mx)

Submission status: Time Limit Exceeded

Solution code:
import copy
from datetime import datetime

#print(datetime.now())
n,k = map(int ,input().split())
p = [[0] * (2*k) for i in range(2*k)]
ans = 0
for i in range(n):
  x,y,c = input().split()
  x = int(x)
  y = int(y)
  if c == 'B':
    x += k
  p[x%(2*k)][y%(2*k)] += 1
#[print(p[i]) for i in range(2*k)]
#print()
#print(datetime.now())

csum1 = copy.deepcopy(p)
for i in range(2*k):
    for j in range(1, k):
        csum1[i][0] += p[i][j]
    for j in range(1, 2*k):
        csum1[i][j] = csum1[i][j-1] - p[i][j-1] + p[i][(j+k-1)%(2*k)]
#print(datetime.now())
#[print(csum1[i]) for i in range(2*k)]
#print()

csum2 = copy.deepcopy(csum1)
#print(datetime.now())
for j in range(2*k):
    for i in range(1, k):
        csum2[0][j] += csum1[i][j]
    for i in range(1, 2*k):
        csum2[i][j] = csum2[i-1][j] - csum1[i-1][j] + csum1[(i+k-1)%(2*k)][j]

#[print(csum2[i]) for i in range(2*k)]
#print(datetime.now())
for i in range(2*k):
    for j in range(2*k):
        ans = max(ans, csum2[i][j] + csum2[(i+k)%(2*k)][(j+k)%(2*k)])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int, input().split())
K2 = K * 2
B = np.zeros((K2+1, K2+1), dtype=np.int32)
for _ in range(N):
    X, Y, C = input().split()
    X, Y = int(X), int(Y)
    if C == "W":
        X += K
    B[X%K2+1][Y%K2+1] += 1
BS = B.sum()
B.cumsum(0, out=B)
B.cumsum(1, out=B)
ans = 0
def get2a(x1, x2, y1, y2): # [x1,x2] x [y1,y2]
    return B[x2][y2] - B[x1][y2] - B[x2][y1] + B[x1][y1]
for i in range(K):
    for j in range(K): # [i,i+K] x [j,j+K]
        b=get2a(i,i+K,0,K2)+get2a(0,K2,j,j+K)-2*get2a(i,i+K,j,j+K)
        ans = max(BS-b,b,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
K2 = K * 2
BS = 0
B = [[0] * K2 for _ in range(K2)]
for _ in range(N):
    X, Y, C = input().split()
    X, Y = int(X), int(Y)
    if C == "W":
        X += K
    B[X%K2][Y%K2] += 1
    BS += 1
BA = [[0] * (K2+1) for _ in range(K2+1)]
for i in range(K2):
    for j in range(K2):
        BA[i+1][j+1] = BA[i+1][j] + BA[i][j+1] - BA[i][j] + B[i][j]
ans = 0
def get2a(x1, x2, y1, y2): # [x1,x2] x [y1,y2]
    return BA[x2][y2] - BA[x1][y2] - BA[x2][y1] + BA[x1][y1]
for i in range(K):
    for j in range(K): # [i,i+K] x [j,j+K]
        b=get2a(i,i+K,0,K2)+get2a(0,K2,j,j+K)-2*get2a(i,i+K,j,j+K)
        ans = max(BS-b, b, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
K2 = K * 2
BS, WS = 0, 0
B = [[0] * K2 for _ in range(K2)]
W = [[0] * K2 for _ in range(K2)]
for _ in range(N):
    X, Y, C = input().split()
    X, Y = int(X), int(Y)
    if C == "B":
        B[X%K2][Y%K2] += 1
        BS += 1
    else:
        W[X%K2][Y%K2] += 1
        WS += 1
BA = [[0] * (K2+1) for _ in range(K2+1)]
WA = [[0] * (K2+1) for _ in range(K2+1)]
for i in range(K2):
    for j in range(K2):
        BA[i+1][j+1] = BA[i+1][j] + BA[i][j+1] - BA[i][j] + B[i][j]
        WA[i+1][j+1] = WA[i+1][j] + WA[i][j+1] - WA[i][j] + W[i][j]
ans = 0
def get2a(T, x1, x2, y1, y2): # [x1,x2] x [y1,y2]
    return T[x2][y2] - T[x1][y2] - T[x2][y1] + T[x1][y1]
for i in range(K):
    for j in range(K): # [i,i+K] x [j,j+K]
        b=get2a(BA,i,i+K,0,K2)+get2a(BA,0,K2,j,j+K)-2*get2a(BA, i, i+K, j, j+K)
        w=get2a(WA,i,i+K,0,K2)+get2a(WA,0,K2,j,j+K)-2*get2a(WA, i, i+K, j, j+K)
        ans = max(b+WS-w, ans)
        ans = max(BS-b+w, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
b=[[0]*k for _ in range(k)]
w=[[0]*k for _ in range(k)]
anb=[[0]*k for _ in range(k)]
anw=[[0]*k for _ in range(k)]
ans=0
i=0
while i<n:
    m=(((int(l[i][0]))//k)+((int(l[i][1]))//k))%2
    if (m==0 and str(l[i][2])=="W"):
        w[int(l[i][0])%k][int(l[i][1])%k]+=1 
    elif (m==1 and str(l[i][2])=="B"):
        b[int(l[i][0])%k][int(l[i][1])%k]+=1
    elif (m==1 and str(l[i][2])=="W"):
        anw[int(l[i][0])%k][int(l[i][1])%k]+=1
    else:
        anb[int(l[i][0])%k][int(l[i][1])%k] +=1

from numpy import matrix

w=matrix(w)
b=matrix(b)
anw=matrix(anw)
anb=matrix(anb)

for a in range(0,k):
     for b in range(0,k):
         total=w[a:k][b:k].sum()+anw[0:a][0:b].sum()+b[a:k][b:k].sum()+anb[0:a][0:b].sum()
         ans=max(ans,total,n-total)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
ans=0
for a in range(0,k):
     for b in range(0,k):
         i=0
         total=0
         while i<n:
           m=(((int(l[i][0])-a)//k)+((int(l[i][1])-b)//k))%2
           if (m==0 and str(l[i][2])=="W") or (m==1 and str(l[i][2])=="B"):
               total=total+1
               i=i+1
           else:
               i=i+1

         else:
              ans=max(ans,total,n-total)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
ans=0
for a in range(0,k):
     for b in range(0,k):
         i=0
         total=0
         while i<n:
           m=(((int(l[i][0])-a)//k)%2)+(((int(l[i][1])-b)//k)%2)
           if (m%2==0 and str(l[i][2])=="W") or (m%2==1 and str(l[i][2])=="B"):
               total=total+1
               i=i+1
           else:
               i=i+1

         else:
              ans=max(ans,total,n-total)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
ans=0
for a in range(0,k):
     for b in range(0,k):
         i=0
         total=0
         while i<n:
           m=((int(l[i][0])-a)//k)%2
           h=((int(l[i][1])-b)//k)%2
           if ((m+h)%2==0 and str(l[i][2])=="W") or ((m+h)%2==1 and str(l[i][2])=="B"):
               total=total+1
               i=i+1
           else:
               i=i+1

         else:
              ans=max(ans,total,n-total)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l=[]
for j in range(0,n):
    l.append(input().split())
ans=0
for a in range(0,k):
     for b in range(0,k):
         i=0
         total=0
         while i<n:
           m=((int(l[i][0])-a)//k)%2
           h=((int(l[i][1])-b)//k)%2
           if ((m+h)%2==0 and str(l[i][2])=="W") or ((m+h)%2==1 and str(l[i][2])=="B"):
               total=total+1
               i=i+1
           else:
               i=i+1

         else:
              ans=max(ans,total,n-total)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import accumulate as ac
    n,k=map(int,input().split())
    kk=2*k
    xyc=[input().split() for _ in [0]*n]
    b=[[0]*(kk+1) for _ in [0]*(kk+1)]
    w=[[0]*(kk+1) for _ in [0]*(kk+1)]
    for x,y,c in xyc:
        if c=="B":b[int(x)%kk+1][int(y)%kk+1]+=1
        else:b[(int(x)+k)%kk+1][int(y)%kk+1]+=1
    b=[list(ac(i)) for i in b]
    for i in range(1,kk+1):
        for j in range(kk+1):
            b[i][j]+=b[i-1][j]
    ans=0
    for i in range(kk):
        if i==0:
            a_t=((i,i+k,0),(i+k,kk,1))
        elif i<k:
            a_t=((0,i,-1),(i,i+k,0),(i+k,kk,1))
        elif i==k:
            a_t=((0,i,-1),(i,kk,0))
        else:
            a_t=((0,i-k,-2),(i-k,i,-1),(i,kk,0))
        for j in range(kk):
            if j==0:
                b_t=((j,j+k,0),(j+k,kk,1))
            elif j<k:
                b_t=((0,j,-1),(j,j+k,0),(j+k,kk,1))
            elif j==k:
                b_t=((0,j,-1),(j,kk,0))
            else:
                b_t=((0,j-k,-2),(j-k,j,-1),(j,kk,0))
            black=[]
            for i,j,l in a_t:
                for x,y,z in b_t:
                    if (l+z)%2==0:
                        black.append((i,x,j,y))
            ret=0
            for tx1,ty1,tx2,ty2 in black:
                ret+=b[tx1][ty1]+b[tx2][ty2]-b[tx1][ty2]-b[tx2][ty1]
            ans=max(ans,ret)
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import accumulate as ac
    n,k=map(int,input().split())
    kk=2*k
    xyc=[input().split() for _ in [0]*n]
    def calc(x,y):return (int(x)%kk,int(y)%kk)
    b=[[0]*(kk+1) for _ in [0]*(kk+1)]
    w=[[0]*(kk+1) for _ in [0]*(kk+1)]
    for x,y,c in xyc:
        if c=="B":b[int(x)%kk+1][int(y)%kk+1]+=1
        else:w[int(x)%kk+1][int(y)%kk+1]+=1
    b=[list(ac(i)) for i in b]
    w=[list(ac(i)) for i in w]
    for i in range(1,kk+1):
        for j in range(kk+1):
            b[i][j]+=b[i-1][j]
            w[i][j]+=w[i-1][j]
    ans=0
    for i in range(kk):
        if i==0:
            a_t=((i,i+k,0),(i+k,kk,1))
        elif i<k:
            a_t=((0,i,-1),(i,i+k,0),(i+k,kk,1))
        elif i==k:
            a_t=((0,i,-1),(i,kk,0))
        else:
            a_t=((0,i-k,-2),(i-k,i,-1),(i,kk,0))
        for j in range(kk):
            if j==0:
                b_t=((j,j+k,0),(j+k,kk,1))
            elif j<k:
                b_t=((0,j,-1),(j,j+k,0),(j+k,kk,1))
            elif j==k:
                b_t=((0,j,-1),(j,kk,0))
            else:
                b_t=((0,j-k,-2),(j-k,j,-1),(j,kk,0))
            black=[]
            white=[]
            for i,j,l in a_t:
                for x,y,z in b_t:
                    if (l+z)%2==0:
                        black.append((i,x,j,y))
                    else:
                        white.append((i,x,j,y))
            ret=0
            for tx1,ty1,tx2,ty2 in black:
                ret+=b[tx1][ty1]+b[tx2][ty2]-b[tx1][ty2]-b[tx2][ty1]
            for tx1,ty1,tx2,ty2 in white:
                ret+=w[tx1][ty1]+w[tx2][ty2]-w[tx1][ty2]-w[tx2][ty1]
            ans=max(ans,ret)
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import accumulate as ac
    n,k=map(int,input().split())
    kk=2*k
    xyc=[input().split() for _ in [0]*n]
    def calc(x,y):return (int(x)%kk,int(y)%kk)
    b=[[0]*(kk+1) for _ in [0]*(kk+1)]
    w=[[0]*(kk+1) for _ in [0]*(kk+1)]
    for x,y,c in xyc:
        if c=="B":b[int(x)%kk+1][int(y)%kk+1]+=1
        else:w[int(x)%kk+1][int(y)%kk+1]+=1
    b=[list(ac(i)) for i in b]
    w=[list(ac(i)) for i in w]
    for i in range(1,kk+1):
        for j in range(kk+1):
            b[i][j]+=b[i-1][j]
            w[i][j]+=w[i-1][j]
    ans=0
    for i in range(kk):
        for j in range(kk):
            a_t=((0,max(i-k,0),-2),(max(i-k,0),i,-1),(i,min(i+k,kk),0),(min(i+k,kk),kk,1))
            b_t=((0,max(j-k,0),-2),(max(j-k,0),j,-1),(j,min(j+k,kk),0),(min(j+k,kk),kk,1))
            a_t=[(i,j,l) for i,j,l in a_t if i!=j]
            b_t=[(i,j,l) for i,j,l in b_t if i!=j]
            black=[]
            white=[]
            for i,j,l in a_t:
                for x,y,z in b_t:
                    if (l+z)%2==0:
                        black.append((i,x,j,y))
                    else:
                        white.append((i,x,j,y))
            ret=0
            for tx1,ty1,tx2,ty2 in black:
                ret+=b[tx1][ty1]+b[tx2][ty2]-b[tx1][ty2]-b[tx2][ty1]
            for tx1,ty1,tx2,ty2 in white:
                ret+=w[tx1][ty1]+w[tx2][ty2]-w[tx1][ty2]-w[tx2][ty1]
            ans=max(ans,ret)
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import accumulate as ac
    n,k=map(int,input().split())
    kk=2*k
    xyc=[input().split() for _ in [0]*n]
    def calc(x,y):return (int(x)%kk,int(y)%kk)
    b=[[0]*(kk+1) for _ in [0]*(kk+1)]
    w=[[0]*(kk+1) for _ in [0]*(kk+1)]
    for x,y,c in xyc:
        if c=="B":b[int(x)%kk+1][int(y)%kk+1]+=1
        else:w[int(x)%kk+1][int(y)%kk+1]+=1
    b=[list(ac(i)) for i in b]
    w=[list(ac(i)) for i in w]
    for i in range(1,kk+1):
        for j in range(kk+1):
            b[i][j]+=b[i-1][j]
            w[i][j]+=w[i-1][j]

    def pos(i,j):
        a=((0,max(i-k,0),-2),(max(i-k,0),i,-1),(i,min(i+k,kk),0),(min(i+k,kk),kk,1))
        b=((0,max(j-k,0),-2),(max(j-k,0),j,-1),(j,min(j+k,kk),0),(min(j+k,kk),kk,1))
        a=[(i,j,l) for i,j,l in a if i!=j]
        b=[(i,j,l) for i,j,l in b if i!=j]
        ret=[]
        for i,j,l in a:
            for x,y,z in b:
                if (l+z)%2==0:
                    ret.append((i,x,j,y))
        return ret

    def calc(i,j):
        ret=0
        for tx1,ty1,tx2,ty2 in pos(i,j):
            ret+=b[tx1][ty1]+b[tx2][ty2]-b[tx1][ty2]-b[tx2][ty1]
        for tx1,ty1,tx2,ty2 in pos((i+k)%kk,j):
            ret+=w[tx1][ty1]+w[tx2][ty2]-w[tx1][ty2]-w[tx2][ty1]
        return ret

    ans=0
    for i in range(kk):
        for j in range(kk):
            ans=max(ans,calc(i,j))
    print(ans)
main()

Submission status: Time Limit Exceeded

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

data = []

for i in range(N):
  (x,y,c) = map(str, input().split())
  x = int(x)
  y = int(y)
  data.append((x,y,c))

result = -1

for i in range(K):
  for j in range(K):
    cnt = 0
    for d in data:
      x,y = d[0] +i, d[1] +j
      xs = (x//K) % 2
      ys = (y//K) % 2
#      print('#', x, y, xs, ys, d[0],d[1],d[2])
      if (xs == ys and d[2]=='B') or (xs != ys and d[2] =='W'):
        cnt+=1
#    print('##', K,cnt,result)
    if N - cnt > cnt:
      cnt = N - cnt
    
    if result < cnt:
      result = cnt

print(result)