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:
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 shift in itertools.product(range(K), range(K)):
    count_1 = 0
    count_2 = 0

    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 maxim < count_1:
        maxim = count_1
    if maxim < count_2:
        maxim = count_2

    if maxim == N:
        break

print(maxim)

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools

def isBlack(K, shift, pos):
    x, y = tuple(x + y for (x, y) in zip(pos, shift))

    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 shift in itertools.product(range(K), range(K)):
    count_1 = 0
    count_2 = 0

    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 maxim < count_1:
        maxim = count_1
    if maxim < count_2:
        maxim = count_2

    if maxim == N:
        break

print(maxim)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

ans=0
k2=2*k


x=[0]*n
y=[0]*n
c=['']*n
for i in range(n):
    x[i],y[i],c[i]=input().split()
    x[i]=int(x[i])%k2
    y[i]=int(y[i])%k2

for x_b,y_b in product(range(k),repeat=2):
    ans_=sum(c[i]=='B' if((x_b<=x[i]<x_b+k) ^ (y_b<=y[i]<y_b+k)) else c[i]=='W' for i in range(n))
    ans=max(ans,ans_,n-ans_)

print(ans)

Submission status: Time Limit Exceeded

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

plan = []

for i in range(N):
    num = raw_input().split()
    plan.append(num)

max_plan = 0

for i in range(K*K):
    org_x = i % K
    org_y = i / K

#    print 'In' + str(org_x) + ',' + str(org_y)

    tmp_max = 0

    tmp_plan = plan[:]
    
    avalable_num = 0

    while len(tmp_plan) > 0:
        p = tmp_plan.pop(0)
#        print p
        p_x = int(p[0])
        p_y = int(p[1])
        p_c = p[2]

        if ((p_c == 'W')and (
                (((p_x + org_x) / K) + ((p_y + org_y) / K)) % 2 == 0)
            or (p_c == 'B')and (
                (((p_x + org_x) / K) + ((p_y + org_y) / K)) % 2 == 1)):
            avalable_num += 1

    if avalable_num > (N / 2):
        tmp_max = avalable_num
    else:
        tmp_max = N - avalable_num

    if tmp_max > max_plan:
        max_plan = tmp_max

print max_plan

Submission status: Time Limit Exceeded

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

ls = [list(input().split(' ')) for _ in range(N)]

color = ['B', 'W'] 

def check_color(x_std, y_std, c_std, x, y):
    if (((x - x_std) // K) + ((y - y_std) // K)) % 2 == 0:
        if c_std == 'B':
            return 'B'
        else:
            return 'W'
    else:
        if c_std == 'B':
            return 'W'
        else:
            return 'B'     

combi = []
for i in range(K):
    for j in range(K):
        combi.append((0 - i, 0 - j))        

cnt_max = 0
for i in range(len(combi)):
    if cnt_max == N:
        break
    else:
        (x_std, y_std) = combi[i]
        for c_std in color:
            cnt_tmp = 0
            for (x, y, c) in ls:
                if check_color(x_std, y_std, c_std, int(x), int(y)) == c:
                    cnt_tmp += 1

            if cnt_tmp >= cnt_max:
                cnt_max = cnt_tmp
                    
        
print(cnt_max)

Submission status: Time Limit Exceeded

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(K+1):
    for j in range(K+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: Time Limit Exceeded

Solution code:
import sys
import math
import itertools

def isBlack(K, shift, pos):
    x, y = tuple(x + y for (x, y) in zip(pos, shift))

    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 shift in itertools.product(range(K*2-1), range(K*2-1)):
    count = 0

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

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

    if maxim < count:
        maxim = count
        max_shift = shift

    if maxim == N:
        break

print(maxim)

Submission status: Time Limit Exceeded

Solution code:
n, k = (int(x) for x in input().split())
kk = 2*k
l = [[0]*k for _ in range(kk)]
for _ in range(n):
    sp = input().split()
    x = int(sp[0])
    y = int(sp[1])
    if sp[2] == 'B':
        x += k
    x %= kk
    y %= kk
    if y >= k:
        y -= k
        if x >= k:
            x -= k
        else:
            x += k
    l[x][y] += 1
sl = [sum(x) for x in l]
l = l + l
m = 0
svl = [[0]*k for _ in range(kk)]
for i in range(kk):
    svl[i][0] = sl[i]
    for j in range(k-1):
        svl[i][j+1] = svl[i][j] - l[i][j] + l[i+k][j]
ssl = [[0]*k for _ in range(kk)]
svl = svl + svl
for j in range(k):
    ssl[0][j] = sum(svl[x][j] for x in range(k))
    for i in range(kk-1):
        ssl[i+1][j] = ssl[i][j] - svl[i][j] + svl[i+k][j]
print(max(max(x) for x in ssl))

Submission status: Time Limit Exceeded

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

ls = [list(input().split(' ')) for _ in range(N)]

color = ['B', 'W'] 

def check_color(x_std, y_std, c_std, x, y):
    if (((x - x_std) // K) + ((y - y_std) // K)) % 2 == 0:
        if c_std == 'B':
            return 'B'
        else:
            return 'W'
    else:
        if c_std == 'B':
            return 'W'
        else:
            return 'B'     

combi = []
for i in range(K):
    for j in range(K):
        combi.append((0 - i, 0 - j))        

cnt_max = 0
for i in range(K * K):
    (x_std, y_std) = combi[i]
    for c_std in color:
        cnt_tmp = 0
        for (x, y, c) in ls:
            if check_color(x_std, y_std, c_std, int(x), int(y)) == c:
                cnt_tmp += 1

        if cnt_tmp >= cnt_max:
            cnt_max = cnt_tmp
        
        
print(cnt_max)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Here your code !
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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

x = []
y = []
c = []
for i in range(N) : 
    s = input().split(" ")
    x.append(int(s[0]))
    y.append(int(s[1]))
    c.append(s[2])

rst = 0
for n in range(K) : 
    for m in range(K) : 
        nice = 0
        nice2 = 0
        for i in range(N) : 
            X = int((x[i] + n) / K)
            Y = int((y[i] + m) / K)
            if ( (X + Y) % 2 == 0) & (c[i] == "B")  : nice += 1  
            elif ( (X + Y) % 2 == 1) & (c[i] == "B")  : nice2 += 1 
            elif ( (X + Y) % 2 == 1) & (c[i] == "W")  : nice += 1  
            elif ( (X + Y) % 2 == 0) & (c[i] == "W")  : nice2 += 1 
        
        NICE = max(nice , nice2)
        if NICE > rst : rst = NICE
print(rst)

Submission status: Memory Limit Exceeded

Solution code:
import numpy as np
from itertools import product

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

    grid = grid.cumsum(axis=1).cumsum(axis=0)
    grid = grid[0:2*K, 0:2*K] + grid[2*K:4*K, 0:2*K] + grid[0:2*K, 2*K:4*K] + grid[2*K:4*K, 2*K:4*K]
    ans = np.amax(grid)
    print(ans)

main()

Submission status: Memory Limit Exceeded

Solution code:
import numpy as np
from itertools import product

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

    grid = grid.cumsum(axis=1).cumsum(axis=0)
    grid = grid[0:2*K, 0:2*K] + grid[2*K:4*K, 0:2*K] + grid[0:2*K, 2*K:4*K] + grid[2*K:4*K, 2*K:4*K]
    ans = np.amax(grid)
    print(ans)

main()

Submission status: Memory Limit Exceeded

Solution code:
N, K = map(int, input().split())
import numpy as np
#対称性を利用して点を単位格子2K*2Kに圧縮
_2K, _4K = 2*K, 4*K
shape = (_4K+1,_4K+1) #後で2K*2Kに圧縮する
Grd = np.zeros(shape,dtype='int64')
for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'B':
        x, y = x%_2K, y%_2K
    else: 
        x, y = (x+K)%_2K, y%_2K
    #この点がK*Kの黒色正方形内に入る。正方形を特徴づけるには左下の座標だけで十分。
    #⇒１つの点はK**2個の塗り方に+1の影響を与える。
    #毎回2K**2のマスにアクセスするとTLEするため、あとで累積和(計算量O(K**2))を取った時に+1される範囲が等しくなるように調整する(隣接差分を取る)。
    #K=3の場合
    #[[1 1 1 0 0 0]    [[ 1 0 0 -1 0 0  0]
    # [1 1 1 0 0 0]     [ 0 0 0  0 0 0  0]
    # [1 1 1 0 0 0]  => [ 0 0 0  0 0 0  0]
    # [0 0 0 1 1 1]     [-1 0 0  2 0 0 -1]
    # [0 0 0 1 1 1]     [ 0 0 0  0 0 0  0]
    # [0 0 0 1 1 1]]    [ 0 0 0  0 0 0  0]
    #                   [ 0 0 0 -1 0 0  1]
    Grd[y, x] += 1
    Grd[y+K, x+K] += 2
    Grd[y+_2K, x+_2K] += 1
    Grd[y+K, x] += -1
    Grd[y, x+K] += -1
    Grd[y+K, x+_2K] += -1
    Grd[y+_2K, x+K] += -1
del x, y, c

#2重累積和計算
Grd = Grd.cumsum()
Grd = Grd.reshape(shape)
Grd = Grd.T.cumsum()
Grd = Grd.reshape(shape)
#2K*2Kに圧縮
Grd = Grd[:_2K,:_2K] +Grd[_2K:_4K,:_2K] +Grd[:_2K,_2K:_4K] +Grd[_2K:_4K,_2K:_4K]

ans = Grd.max()
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
N, K = map(int, input().split())
import numpy as np
#対称性を利用して点を単位格子2K*2Kに圧縮
_2K, _4K = 2*K, 4*K
shape = (_4K+1,_4K+1) #後で2K*2Kに圧縮する
Grd = np.zeros(shape,dtype='int64')
for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'B':
        x, y = x%_2K, y%_2K
    else: 
        x, y = (x+K)%_2K, y%_2K
    #この点がK*Kの黒色正方形内に入る。正方形を特徴づけるには左下の座標だけで十分。
    #⇒１つの点はK**2個の塗り方に+1の影響を与える。
    #毎回2K**2のマスにアクセスするとTLEするため、あとで累積和(計算量O(K**2))を取った時に+1される範囲が等しくなるように調整する(隣接差分を取る)。
    #K=3の場合
    #[[1 1 1 0 0 0]    [[ 1 0 0 -1 0 0  0]
    # [1 1 1 0 0 0]     [ 0 0 0  0 0 0  0]
    # [1 1 1 0 0 0]  => [ 0 0 0  0 0 0  0]
    # [0 0 0 1 1 1]     [-1 0 0  2 0 0 -1]
    # [0 0 0 1 1 1]     [ 0 0 0  0 0 0  0]
    # [0 0 0 1 1 1]]    [ 0 0 0  0 0 0  0]
    #                   [ 0 0 0 -1 0 0  1]
    Grd[y, x] += 1
    Grd[y+K, x+K] += 2
    Grd[y+_2K, x+_2K] += 1
    Grd[y+K, x] += -1
    Grd[y, x+K] += -1
    Grd[y+K, x+_2K] += -1
    Grd[y+_2K, x+K] += -1
del x, y, c

#2重累積和計算
Grd = Grd.cumsum().reshape(shape)
Grd = Grd.T.cumsum().reshape(shape)
#2K*2Kに圧縮
Grd = Grd[:_2K,:_2K] +Grd[_2K:_4K,:_2K] +Grd[:_2K,_2K:_4K] +Grd[_2K:_4K,_2K:_4K]

ans = Grd.max()
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
N, K = map(int, input().split())
import numpy as np
#対称性を利用して点を単位格子2K*2Kに圧縮
_2K, _4K = 2*K, 4*K
shape = (_4K+1,_4K+1) #後で2K*2Kに圧縮する
Grd = np.zeros(shape,dtype='int64')
for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'B':
        x, y = x%_2K, y%_2K
    else: 
        x, y = (x+K)%_2K, y%_2K
    #この点がK*Kの黒色正方形内に入る。正方形を特徴づけるには左下の座標だけで十分。
    #⇒１つの点はK**2個の塗り方に+1の影響を与える。
    #毎回2K**2のマスにアクセスするとTLEするため、あとで累積和(計算量O(K**2))を取った時に+1される範囲が等しくなるように調整する(隣接差分を取る)。
    #K=3の場合
    #[[1 1 1 0 0 0]    [[ 1 0 0 -1 0 0  0]
    # [1 1 1 0 0 0]     [ 0 0 0  0 0 0  0]
    # [1 1 1 0 0 0]  => [ 0 0 0  0 0 0  0]
    # [0 0 0 1 1 1]     [-1 0 0  2 0 0 -1]
    # [0 0 0 1 1 1]     [ 0 0 0  0 0 0  0]
    # [0 0 0 1 1 1]]    [ 0 0 0  0 0 0  0]
    #                   [ 0 0 0 -1 0 0  1]
    Grd[y, x] += 1
    Grd[y+K, x+K] += 2
    Grd[y+_2K, x+_2K] += 1
    Grd[y+K, x] += -1
    Grd[y, x+K] += -1
    Grd[y+K, x+_2K] += -1
    Grd[y+_2K, x+K] += -1
del x, y, c

#2重累積和計算
Grd = Grd.cumsum().reshape(shape)
Grd = Grd.T.cumsum().reshape(shape)
#2K*2Kに圧縮
Grd = Grd[:_2K,:] + Grd[_2K:_4K,:]
Grd = Grd[:,:_2K] + Grd[:,_2K:_4K]

ans = Grd.max()
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
N, K = map(int, input().split())
import numpy as np
#対称性を利用して点を単位格子2K*2Kに圧縮
_2K, _4K = 2*K, 4*K
shape = (_4K+1,_4K+1) #後で2K*2Kに圧縮する
Grd = np.zeros(shape,dtype='int64')
for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'B':
        x, y = x%_2K, y%_2K
    else: 
        x, y = (x+K)%_2K, y%_2K
    #この点がK*Kの黒色正方形内に入る。正方形を特徴づけるには左下の座標だけで十分。
    #⇒１つの点はK**2個の塗り方に+1の影響を与える。
    #毎回2K**2のマスにアクセスするとTLEするため、あとで累積和(計算量O(K**2))を取った時に+1される範囲が等しくなるように調整する(隣接差分を取る)。
    #K=3の場合
    #[[1 1 1 0 0 0]    [[ 1 0 0 -1 0 0  0]
    # [1 1 1 0 0 0]     [ 0 0 0  0 0 0  0]
    # [1 1 1 0 0 0]  => [ 0 0 0  0 0 0  0]
    # [0 0 0 1 1 1]     [-1 0 0  2 0 0 -1]
    # [0 0 0 1 1 1]     [ 0 0 0  0 0 0  0]
    # [0 0 0 1 1 1]]    [ 0 0 0  0 0 0  0]
    #                   [ 0 0 0 -1 0 0  1]
    Grd[y, x] += 1
    Grd[y+K, x+K] += 2
    Grd[y+_2K, x+_2K] += 1
    Grd[y+K, x] += -1
    Grd[y, x+K] += -1
    Grd[y+K, x+_2K] += -1
    Grd[y+_2K, x+K] += -1
del x, y, c

#2重累積和計算
Grd = Grd.cumsum().reshape(shape).T.cumsum().reshape(shape)
#2K*2Kに圧縮
Grd = Grd[:_2K,:] + Grd[_2K:_4K,:]
Grd = Grd[:,:_2K] + Grd[:,_2K:_4K]

ans = Grd.max()
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import sys
from itertools import accumulate
def main():
    N, K = map(int, sys.stdin.buffer.readline().split())
    XYC = sys.stdin.buffer.read().split()
    X, Y, C = list(map(int, XYC[::3])), list(map(int, XYC[1::3])), XYC[2::3]
    M = [[0]*(K*4) for _ in range(K*2+1)]
    for x, y, c in zip(X, Y, C):
        if c == b"B":
            x += K
        x %= 2*K
        y %= 2*K
        if x >= K and y >= K:
            x -= K
            y -= K
        elif y >= K:
            y -= K
            x += K
        M[y][x] += 1
        M[y][(x+2*K)%(4*K)] += 1
        M[y+K][x+K] += 1
        M[y+K][(x+3*K)%(4*K)] += 1
        if y == 0:
            M[2*K][x] += 1
            M[2*K][(x+2*K)%(4*K)] += 1
    M = [list(accumulate(m)) for m in M]
    for y, m in enumerate(M[:-1], 1):
        My = M[y]
        for x, mm in enumerate(m):
            My[x] += mm
    ans = max(M[y+K][x+K]+M[y][x]-M[y+K][x]-M[y][x+K] for y in range(K+1) for x in range(2*K+1))
    print(ans)

main()

Submission status: Memory Limit Exceeded

Solution code:
import sys
import array
from itertools import accumulate
input = sys.stdin.readline
N,K = map(int,input().split())
xyc = []
for i in range(N):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    xyc.append([x % (2*K), y % (2*K), c])

wmap = [array.array('I',[0]*3*K) for i in [0]*3*K]
hmap = [array.array('I',[0]*3*K) for i in [0]*3*K]
for x,y,c in xyc:
    if c == 'W':
        wmap[y][x] += 1
        if y < K:
            wmap[y+2*K][x] += 1
        if x < K:
            wmap[y][x+2*K] += 1
        if x < K and y < K:
            wmap[y+2*K][x+2*K] += 1
    else:
        hmap[y][x] += 1
        if x < K:
            hmap[y][x+2*K] += 1
        if y < K:
            hmap[y+2*K][x] += 1
        if x < K and y < K:
            hmap[y+2*K][x+2*K] += 1

wcumsum = [array.array('I',[0]*(3*K+1))] + [array.array('I',[0]+list(accumulate(row))) for row in wmap]
hcumsum = [array.array('I',[0]*(3*K+1))] + [array.array('I',[0]+list(accumulate(row))) for row in hmap]

for y in range(1,3*K+1):
    for x in range(3*K+1):
        wcumsum[y][x] += wcumsum[y-1][x]
        hcumsum[y][x] += hcumsum[y-1][x]

def cs2(m, ltx, lty, rbx, rby):
    S = m[rby-1][rbx-1]
    S -= m[rby-1][ltx-1]
    S -= m[lty-1][rbx-1]
    S += m[lty-1][ltx-1]
    return S

ans = 0
for y in range(1,K+1):
    for x in range(1,K+1):
        ltw = cs2(wcumsum,x,y,x+K, y+K)
        rbw = cs2(wcumsum,x+K,y+K,x+2*K, y+2*K)
        lbh = cs2(hcumsum,x,y+K,x+K, y+2*K)
        rth = cs2(hcumsum,x+K,y,x+2*K, y+K)
        temp = ltw + rbw + lbh + rth
        ans = max(ans,temp)

        ltw = cs2(hcumsum,x,y,x+K, y+K)
        rbw = cs2(hcumsum,x+K,y+K,x+2*K, y+2*K)
        lbh = cs2(wcumsum,x,y+K,x+K, y+2*K)
        rth = cs2(wcumsum,x+K,y,x+2*K, y+K)
        temp = ltw + rbw + lbh + rth
        ans = max(ans,temp)

print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import sys
import array
from itertools import accumulate
input = sys.stdin.readline
N,K = map(int,input().split())
xyc = []
for i in range(N):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    xyc.append([x % (2*K), y % (2*K), c])

wmap = [[0]*3*K for i in [0]*3*K]
hmap = [[0]*3*K for i in [0]*3*K]
for x,y,c in xyc:
    if c == 'W':
        wmap[y][x] += 1
        if y < K:
            wmap[y+2*K][x] += 1
        if x < K:
            wmap[y][x+2*K] += 1
        if x < K and y < K:
            wmap[y+2*K][x+2*K] += 1
    else:
        hmap[y][x] += 1
        if x < K:
            hmap[y][x+2*K] += 1
        if y < K:
            hmap[y+2*K][x] += 1
        if x < K and y < K:
            hmap[y+2*K][x+2*K] += 1

wcumsum = [[0]*(3*K+1)] + [[0]+list(accumulate(row)) for row in wmap]

for y in range(1,3*K+1):
    for x in range(3*K+1):
        wcumsum[y][x] += wcumsum[y-1][x]

def cs2(m, ltx, lty, rbx, rby):
    S = m[rby-1][rbx-1]
    S -= m[rby-1][ltx-1]
    S -= m[lty-1][rbx-1]
    S += m[lty-1][ltx-1]
    return S

ans = 0
vals = [[[0]*2 for j in range(K)] for i in range(K)]
for y in range(1,K+1):
    for x in range(1,K+1):
        ltw = cs2(wcumsum,x,y,x+K, y+K)
        rbw = cs2(wcumsum,x+K,y+K,x+2*K, y+2*K)
        temp = ltw + rbw
        vals[y-1][x-1][0] += temp

        lbh = cs2(wcumsum,x,y+K,x+K, y+2*K)
        rth = cs2(wcumsum,x+K,y,x+2*K, y+K)
        temp = lbh + rth
        vals[y-1][x-1][1] += temp

wcumsum = [[0]*(3*K+1)] + [[0]+list(accumulate(row)) for row in hmap]
for y in range(1,3*K+1):
    for x in range(3*K+1):
        wcumsum[y][x] += wcumsum[y-1][x]

for y in range(1,K+1):
    for x in range(1,K+1):
        ltw = cs2(wcumsum,x,y,x+K, y+K)
        rbw = cs2(wcumsum,x+K,y+K,x+2*K, y+2*K)
        temp = ltw + rbw
        vals[y-1][x-1][1] += temp

        lbh = cs2(wcumsum,x,y+K,x+K, y+2*K)
        rth = cs2(wcumsum,x+K,y,x+2*K, y+K)
        temp = lbh + rth
        vals[y-1][x-1][0] += temp

ans = 0
for y in range(K):
    for x in range(K):
        for m in range(2):
            ans = max(ans, vals[y][x][m])
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import sys
from itertools import accumulate
input = sys.stdin.readline
N,K = map(int,input().split())
xyc = []
for i in range(N):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    xyc.append([x % (2*K), y % (2*K), c])

wmap = [[0]*3*K for i in [0]*3*K]
hmap = [[0]*3*K for i in [0]*3*K]
for x,y,c in xyc:
    if c == 'W':
        wmap[y][x] += 1
        if y < K:
            wmap[y+2*K][x] += 1
        if x < K:
            wmap[y][x+2*K] += 1
        if x < K and y < K:
            wmap[y+2*K][x+2*K] += 1
    else:
        hmap[y][x] += 1
        if x < K:
            hmap[y][x+2*K] += 1
        if y < K:
            hmap[y+2*K][x] += 1
        if x < K and y < K:
            hmap[y+2*K][x+2*K] += 1

wcumsum = [[0]*(3*K+1)] + [[0]+list(accumulate(row)) for row in wmap]
del wmap
hcumsum = [[0]*(3*K+1)] + [[0]+list(accumulate(row)) for row in hmap]
del hmap
for y in range(1,3*K+1):
    for x in range(3*K+1):
        wcumsum[y][x] += wcumsum[y-1][x]
        hcumsum[y][x] += hcumsum[y-1][x]
#[print(row) for row in wmap]
#[print(row) for row in wcumsum]

def cs2(m, ltx, lty, rbx, rby):
    S = m[rby-1][rbx-1]
    S -= m[rby-1][ltx-1]
    S -= m[lty-1][rbx-1]
    S += m[lty-1][ltx-1]
    return S

ans = 0
for y in range(1,K+1):
    for x in range(1,K+1):
        ltw = cs2(wcumsum,x,y,x+K, y+K)
        rbw = cs2(wcumsum,x+K,y+K,x+2*K, y+2*K)
        lbh = cs2(hcumsum,x,y+K,x+K, y+2*K)
        rth = cs2(hcumsum,x+K,y,x+2*K, y+K)
        temp = ltw + rbw + lbh + rth
        ans = max(ans,temp)

        ltw = cs2(hcumsum,x,y,x+K, y+K)
        rbw = cs2(hcumsum,x+K,y+K,x+2*K, y+2*K)
        lbh = cs2(wcumsum,x,y+K,x+K, y+2*K)
        rth = cs2(wcumsum,x+K,y,x+2*K, y+K)
        temp = ltw + rbw + lbh + rth
        ans = max(ans,temp)

print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import sys
from itertools import accumulate
input = sys.stdin.readline
N,K = map(int,input().split())
xyc = []
for i in range(N):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    xyc.append([x % (2*K), y % (2*K), c])

wmap = [[0]*4*K for i in [0]*4*K]
hmap = [[0]*4*K for i in [0]*4*K]
for x,y,c in xyc:
    if c == 'W':
        wmap[y][x] += 1
        wmap[y+2*K][x] += 1
        wmap[y][x+2*K] += 1
        wmap[y+2*K][x+2*K] += 1
    else:
        hmap[y][x] += 1
        hmap[y][x+2*K] += 1
        hmap[y+2*K][x] += 1
        hmap[y+2*K][x+2*K] += 1

wcumsum = [[0]*(4*K+1)] + [[0]+list(accumulate(row)) for row in wmap]
del wmap
hcumsum = [[0]*(4*K+1)] + [[0]+list(accumulate(row)) for row in hmap]
del hmap
for y in range(1,4*K+1):
    for x in range(4*K+1):
        wcumsum[y][x] += wcumsum[y-1][x]
        hcumsum[y][x] += hcumsum[y-1][x]
#[print(row) for row in wmap]
#[print(row) for row in wcumsum]

def cs2(m, ltx, lty, rbx, rby):
    S = m[rby-1][rbx-1]
    S -= m[rby-1][ltx-1]
    S -= m[lty-1][rbx-1]
    S += m[lty-1][ltx-1]
    return S

ans = 0
for y in range(1,K+1):
    for x in range(1,K+1):
        ltw = cs2(wcumsum,x,y,x+K, y+K)
        rbw = cs2(wcumsum,x+K,y+K,x+2*K, y+2*K)
        lbh = cs2(hcumsum,x,y+K,x+K, y+2*K)
        rth = cs2(hcumsum,x+K,y,x+2*K, y+K)
        temp = ltw + rbw + lbh + rth
        ans = max(ans,temp)

        ltw = cs2(hcumsum,x,y,x+K, y+K)
        rbw = cs2(hcumsum,x+K,y+K,x+2*K, y+2*K)
        lbh = cs2(wcumsum,x,y+K,x+K, y+2*K)
        rth = cs2(wcumsum,x+K,y,x+2*K, y+K)
        temp = ltw + rbw + lbh + rth
        ans = max(ans,temp)

print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n,k = list(map(int, input().split()))
v = [[0]*(4*k) for _ in range(4*k)]

for i in range(n):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    if c=="B":
        x += k
    x %= 2*k
    y %= 2*k
    v[x][y] += 1
    v[x][y+2*k] += 1
    v[x+2*k][y] += 1
    v[x+2*k][y+2*k] += 1
def cumsum2(v):
    # v: h*wの2次元リスト
    h,w = len(v), len(v[0])
    v.insert(0, [0]*w)
    for l in v:
        l.insert(0, 0)
    for i in range(1,h+1):
        for j in range(1,w+1):
            v[i][j] = v[i-1][j] + v[i][j-1] - v[i-1][j-1] + v[i][j]
    return v
cumsum2(v)
ans = -1
for i in range(2*k):
    for j in range(2*k):
        val0 = v[i+k][j+k]-v[i+k][j]-v[i][j+k]+v[i][j] + v[i+2*k][j+2*k]-v[i+2*k][j+k]-v[i+k][j+2*k]+v[i+k][j+k]
#         val1 = v[i+2*k][j+k]-v[i+2*k][j]-v[i+k][j+k]+v[i+k][j] + v[i+k][j+2*k]-v[i+k][j+k]-v[i][j+2*k]+v[i][j+k]
        ans = max(ans, val0)
print(ans)

Submission status: Memory Limit Exceeded

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


def main():
    n, k = map(int, input().split())
    
    white = [[0]*(4*k+1) for _ in range(4*k+1)]
    black = [[0]*(4*k+1) for _ in range(4*k+1)]
    for i in range(n):
        x, y, z = input().split()
        if z == "B":
            black[int(x)%(2*k)+1][int(y)%(2*k)+1] += 1
            black[int(x)%(2*k)+1+2*k][int(y)%(2*k)+1] += 1
            black[int(x)%(2*k)+1][int(y)%(2*k)+1+2*k] += 1
            black[int(x)%(2*k)+1+2*k][int(y)%(2*k)+1+2*k] += 1
        else:
            white[int(x)%(2*k)+1][int(y)%(2*k)+1] += 1
            white[int(x)%(2*k)+1+2*k][int(y)%(2*k)+1] += 1
            white[int(x)%(2*k)+1][int(y)%(2*k)+1+2*k] += 1
            white[int(x)%(2*k)+1+2*k][int(y)%(2*k)+1+2*k] += 1
    
    for i in range(4*k):
        for j in range(4*k):
            white[i+1][j+1] += white[i][j+1]+white[i+1][j]-white[i][j]
            black[i+1][j+1] += black[i][j+1]+black[i+1][j]-black[i][j]
    
    
    ans = 0
    for i in range(2*k):
        for j in range(2*k):
            p, q = i+k, j+k
            x, y = i+2*k, j+2*k
            sub = white[p][q]+white[i][j]-white[p][j]-white[i][q]\
                 +white[x][y]+white[p][q]-white[x][q]-white[p][y]\
                 +black[x][q]+black[p][j]-black[p][q]-black[x][j]\
                 +black[p][y]+black[i][q]-black[i][y]-black[p][q]
            if ans < sub:
                ans = sub
    
    print(ans)

    
    
if __name__ == "__main__":
    main()

Submission status: Memory Limit Exceeded

Solution code:
import sys
import numpy as np

read=sys.stdin.read
readline=sys.stdin.readline

def main():
  def mycount(x1,y1,x2,y2,mat,s):
    return mat[s,x2,y2]-mat[s,x1,y2]-mat[s,x2,y1]+mat[s,x1,y1]
  wb={'W':0,'B':1}
  n,k=map(int,readline().split())
  xyc=[l.split() for l in read().splitlines()]
  xyc=[[int(lst[0]) % (2*k),int(lst[1]) % (2*k),wb[lst[2]]] for lst in xyc]
  mat=np.zeros((2,4*k+1,4*k+1),dtype='int64')
  cand=np.zeros((2,2*k+1,2*k+1),dtype='int64')
  for i in range(4):
    for e in xyc:
      mat[e[2],e[0]+1+2*k*(i&1),e[1]+1+2*k*(i>>1&1)]+=1
  for i in range(1,4*k+1):
      mat[:,:,i]+=mat[:,:,i-1]
  for i in range(1,4*k+1):
      mat[:,i,:]+=mat[:,i-1,:]
 # for i in range(1,4*k+1):
 #   for j in range(1,4*k+1):
 #     mat[:,i,j]=mat[:,i,j]+mat[:,i-1,j]+mat[:,i,j-1]-mat[:,i-1,j-1]
  cand=mat[0,k:3*k+1,k:3*k+1]+mat[0,:2*k+1,:2*k+1]-mat[0,k:3*k+1,:2*k+1]-mat[0,:2*k+1,k:3*k+1]\
      +mat[0,2*k:4*k+1,2*k:4*k+1]+mat[0,k:3*k+1,k:3*k+1]-mat[0,2*k:4*k+1,k:3*k+1]-mat[0,k:3*k+1,2*k:4*k+1]\
      +mat[1,2*k:4*k+1,k:3*k+1]+mat[1,k:3*k+1,:2*k+1]-mat[1,2*k:4*k+1,:2*k+1]-mat[1,k:3*k+1,k:3*k+1]\
      +mat[1,k:3*k+1,2*k:4*k+1]+mat[1,:2*k+1,k:3*k+1]-mat[1,:2*k+1,2*k:4*k+1]-mat[1,k:3*k+1,k:3*k+1]
  #print(mat)
  print(np.max(cand))
  
if __name__=='__main__':
  main()

Submission status: Memory Limit Exceeded

Solution code:
import sys
import numpy as np

read=sys.stdin.read
readline=sys.stdin.readline

def main():
  def mycount(x1,y1,x2,y2,mat,s):
    return mat[s,x2,y2]-mat[s,x1,y2]-mat[s,x2,y1]+mat[s,x1,y1]
  wb={'W':0,'B':1}
  n,k=map(int,readline().split())
  xyc=[l.split() for l in read().splitlines()]
  xyc=[[int(lst[0]) % (2*k),int(lst[1]) % (2*k),wb[lst[2]]] for lst in xyc]
  mat=np.zeros((2,4*k+1,4*k+1),dtype='int64')
  cand=np.zeros((2,2*k+1,2*k+1),dtype='int64')
  for i in range(4):
    for e in xyc:
      mat[e[2],e[0]+1+2*k*(i&1),e[1]+1+2*k*(i>>1&1)]+=1
  mat=np.cumsum(mat,axis=1)
  mat=np.cumsum(mat,axis=2)
  cand=mat[0,k:3*k+1,k:3*k+1]+mat[0,:2*k+1,:2*k+1]-mat[0,k:3*k+1,:2*k+1]-mat[0,:2*k+1,k:3*k+1]\
      +mat[0,2*k:4*k+1,2*k:4*k+1]+mat[0,k:3*k+1,k:3*k+1]-mat[0,2*k:4*k+1,k:3*k+1]-mat[0,k:3*k+1,2*k:4*k+1]\
      +mat[1,2*k:4*k+1,k:3*k+1]+mat[1,k:3*k+1,:2*k+1]-mat[1,2*k:4*k+1,:2*k+1]-mat[1,k:3*k+1,k:3*k+1]\
      +mat[1,k:3*k+1,2*k:4*k+1]+mat[1,:2*k+1,k:3*k+1]-mat[1,:2*k+1,2*k:4*k+1]-mat[1,k:3*k+1,k:3*k+1]
  print(np.max(cand))
  
if __name__=='__main__':
  main()