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

Solution code:
import itertools
import numpy as np
N, K, *XYC = open(0).read().split()
N = int(N)
K = int(K)
board = np.zeros((4 * K + 1, 4 * K + 1), dtype=np.uint16)
for x, y, c in zip(XYC[::3], XYC[1::3], XYC[2::3]):
    x = int(x)
    y = int(y)
    if c == 'W':
        x += K
    x = x % (2 * K)
    y = y % (2 * K)
    board[x, y] += 1
    board[(x + K) % (2 * K), (y + K) % (2 * K)] += 1
board[1 + 2 * K:, 1 + 2 * K:] = board[:2 * K, :2 * K]
board[1:1 + 2 * K, 1 + 2 * K:] = board[1 + 2 * K:, 1 + 2 * K:]
board[1 + 2 * K:, 1:1 + 2 * K] = board[1 + 2 * K:, 1 + 2 * K:]
board[1:1 + 2 * K, 1:1 + 2 * K] = board[1 + 2 * K:, 1 + 2 * K:]
board[0, :] = 0
board[:, 0] = 0
board = np.cumsum(board, axis=0)
board = np.cumsum(board, axis=1)
ans = np.max(board[K:3 * K, K:3 * K] + board[:2 * K, :2 * K] -
             board[:2 * K, K:3 * K] - board[K:3 * K, :2 * K])
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import itertools
import numpy as np
N, K, *XYC = open(0).read().split()
N = int(N)
K = int(K)
board = np.zeros((4 * K + 1, 4 * K + 1), dtype=np.uint16)
for x, y, c in zip(XYC[::3], XYC[1::3], XYC[2::3]):
    x = int(x)
    y = int(y)
    if c == 'W':
        x += K
    x = x % (2 * K)
    y = y % (2 * K)
    board[x, y] += 1
    board[(x + K) % (2 * K), (y + K) % (2 * K)] += 1
board[1 + 2 * K:, 1 + 2 * K:] = board[:2 * K, :2 * K]
board[1:1 + 2 * K, 1 + 2 * K:] = board[1 + 2 * K:, 1 + 2 * K:]
board[1 + 2 * K:, 1:1 + 2 * K] = board[1 + 2 * K:, 1 + 2 * K:]
board[1:1 + 2 * K, 1:1 + 2 * K] = board[1 + 2 * K:, 1 + 2 * K:]
board[0, :] = 0
board[:, 0] = 0
board = np.cumsum(np.cumsum(board, axis=0), axis=1)
ans = np.max(board[K:3 * K, K:3 * K] + board[:2 * K, :2 * K] -
             board[:2 * K, K:3 * K] - board[K:3 * K, :2 * K])
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import itertools
import numpy as np
N, K, *XYC = open(0).read().split()
N = int(N)
K = int(K)
board = np.zeros((2 * K, 2 * K), dtype=np.uint16)
for x, y, c in zip(XYC[::3], XYC[1::3], XYC[2::3]):
    x = int(x)
    y = int(y)
    if c == 'W':
        x += K
    x = x % (2 * K)
    y = y % (2 * K)
    board[x, y] += 1
    board[(x + K) % (2 * K), (y + K) % (2 * K)] += 1
board2 = np.zeros((4 * K + 1, 4 * K + 1), dtype=np.uint16)
for xs, ys in itertools.product([(1, 1 + 2 * K), (1 + 2 * K, 1 + 4 * K)],
                                repeat=2):
    board2[xs[0]:xs[1], ys[0]:ys[1]] = board
board = board2
board = np.cumsum(np.cumsum(board, axis=0), axis=1)
ans = np.max(board[K:3 * K, K:3 * K] + board[:2 * K, :2 * K] -
             board[:2 * K, K:3 * K] - board[K:3 * K, :2 * K])
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import itertools
import numpy as np
N, K, *XYC = open(0).read().split()
N = int(N)
K = int(K)
board = np.zeros((2 * K, 2 * K), dtype=np.uint16)
for x, y, c in zip(XYC[::3], XYC[1::3], XYC[2::3]):
    x = int(x)
    y = int(y)
    if c == 'W':
        x += K
    x = x % (2 * K)
    y = y % (2 * K)
    board[x, y] += 1
    board[(x + K) % (2 * K), (y + K) % (2 * K)] += 1
board2 = np.zeros((4 * K + 1, 4 * K + 1), dtype=np.uint16)
for xs, ys in itertools.product([(1, 1 + 2 * K), (1 + 2 * K, 1 + 4 * K)],
                                repeat=2):
    board2[xs[0]:xs[1], ys[0]:ys[1]] = board
board = board2
cum = np.cumsum(np.cumsum(board, axis=0), axis=1)
ans = np.max(cum[K:3 * K, K:3 * K] + cum[:2 * K, :2 * K] -
             cum[:2 * K, K:3 * K] - cum[K:3 * K, :2 * K])
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import itertools
import numpy as np
N, K, *XYC = open(0).read().split()
N = int(N)
K = int(K)
board = np.zeros((2 * K, 2 * K), dtype=np.uint16)
for x, y, c in zip(XYC[::3], XYC[1::3], XYC[2::3]):
    x = int(x)
    y = int(y)
    if c == 'W':
        x += K
    x = x % (2 * K)
    y = y % (2 * K)
    board[x, y] += 1
    board[(x + K) % (2 * K), (y + K) % (2 * K)] += 1
board2 = np.zeros((4 * K + 1, 4 * K + 1), dtype=np.int64)
for xs, ys in itertools.product([(1, 1 + 2 * K), (1 + 2 * K, 1 + 4 * K)],
                                repeat=2):
    board2[xs[0]:xs[1], ys[0]:ys[1]] = board
board = board2
cum = np.cumsum(np.cumsum(board, axis=0), axis=1)
ans = np.max(cum[K:3 * K, K:3 * K] + cum[:2 * K, :2 * K] -
             cum[:2 * K, K:3 * K] - cum[K:3 * K, :2 * K])
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import itertools
import numpy as np
N, K, *XYC = open(0).read().split()
N = int(N)
K = int(K)
board = np.zeros((2 * K, 2 * K), dtype=np.int64)
for x, y, c in zip(XYC[::3], XYC[1::3], XYC[2::3]):
    x = int(x)
    y = int(y)
    if c == 'W':
        x += K
    x = x % (2 * K)
    y = y % (2 * K)
    board[x, y] += 1
    board[(x + K) % (2 * K), (y + K) % (2 * K)] += 1
board2 = np.zeros((4 * K + 1, 4 * K + 1), dtype=np.int64)
for xs, ys in itertools.product([(1, 1 + 2 * K), (1 + 2 * K, 1 + 4 * K)],
                                repeat=2):
    board2[xs[0]:xs[1], ys[0]:ys[1]] = board
board = board2
cum = np.cumsum(np.cumsum(board, axis=0), axis=1)
ans = np.max(cum[K:3 * K, K:3 * K] + cum[:2 * K, :2 * K] -
             cum[:2 * K, K:3 * K] - cum[K:3 * K, :2 * K])
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
N,K=map(int,input().split())
Z=[[0]*(K*4) for i in range(K*4)]
for i in range(N):
  x,y,c=input().split()
  x,y=int(x),int(y)
  if c=='W':
    y+=K
  x%=2*K
  y%=2*K
  Z[x][y]+=1
  Z[x+K][y]-=1
  Z[x][y+K]-=1
  Z[x+K][y+K]+=2
  Z[x+K+K][y+K]-=1
  Z[x+K][y+K+K]-=1
  Z[x+K+K][y+K+K]+=1
#print(*Z,sep='\n')
C=[[0]*(K*4+1) for i in range(K*4+1)]
for i in range(K*4):
  for j in range(K*4):
    C[i+1][j+1]=C[i+1][j]+C[i][j+1]+Z[i][j]-C[i][j]
#print(*C,sep='\n')
for i in range(K+K):
  for j in range(K+K):
    C[i][j]+=C[i+K+K][j]+C[i][j+K+K]+C[i+K+K][j+K+K]
P=0
for i in range(K*4+1):
  for j in range(K*4+1):
    P=max(P,C[i][j])
print(P)
#print(*C,sep='\n')

Submission status: Memory Limit Exceeded

Solution code:
class Accumulate2D:
    def __init__(self, a):
        self.height = len(a)
        self.width = len(a[0])
        self.acc = self.accumulate(a)

    def accumulate(self,a):
        b = [[0]*(self.width+1) for i in range(self.height+1)]
        b[1][1] = a[0][0]
        for i in range(self.height):
            for j in range(self.width):
                b[i+1][j+1] = b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]
        return b

    def sum(self, p, q):
        y1,x1 = p
        y2,x2 = q
        b = self.acc
        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
k4 = k*4

z = [[0]*k4 for i in range(k4)]

for i in range(n):
    x,y,c = input().split()
    x = int(x) % kk
    y = int(y) % kk
    if c=='W':
        x = (x+k)%kk
    for a in [0,1]:
        for b in [0,1]:
            z[x+a*kk][y+b*kk]+=1


z = Accumulate2D(z)

ans = 0
for i in range(2*k):
    for j in range(2*k):
        a = z.sum([i,j],[i+k-1,j+k-1])\
            + z.sum([i+k,j+k],[i+kk-1,j+kk-1])
        ans = max(ans,a)

print(ans)

Submission status: Memory Limit Exceeded

Solution code:
class Accumulate2D:
    def __init__(self, a):
        self.height = len(a)
        self.width = len(a[0])
        self.acc = self.accumulate(a)

    def accumulate(self,a):
        b = [[0]*(self.width+1) for i in range(self.height+1)]
        b[1][1] = a[0][0]
        for i in range(self.height):
            for j in range(self.width):
                b[i+1][j+1] = b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]
        return b

    def sum(self, p, q):
        y1,x1 = p
        y2,x2 = q
        b = self.acc
        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
k4 = k*4

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

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

B = Accumulate2D(black)
W = Accumulate2D(white)

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

print(ans)

Submission status: Memory 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 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
k4 = k*4

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

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

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

ans = 0
for i in range(2*k):
    for j in range(2*k):
        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: Memory Limit Exceeded

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

def main():
    N, K = map(int, input().split())
    L = 2*K
    state = [[0, 0] for _ in range((L+1)*(K+1))]

    for _ in range(N):
        x, y, c = map(str, input().split())
        a, b = int(x)%L, int(y)%L
        k = 0 if c == 'W' else 1
        if a >= K:
            if b >= K:
                a -= K
                b -= K
            else:
                a -= K
                b += K
        state[(a+1)*(L+1)+b+1][k] += 1


    for i in range(K):
        for j in range(L):
            for k in [0, 1]:
                state[(i+1)*(L+1)+j+1][k] += state[(i+1)*(L+1)+j][k] + state[i*(L+1)+j+1][k] - state[i*(L+1)+j][k]

    P = L+1
    ans = 0
    for x in range(K):
        for y in range(K):
            for k in [0, 1]:
                count = 0
                count += state[x*P+y][k]
                count += state[x*P+L][k] - state[x*P+y+K][k]
                count += state[K*P+y+K][k] - state[x*P+y+K][k] - state[K*P+y][k] + state[x*P+y][k]

                l = k ^ 1
                count += state[K*P+y][l] - state[x*P+y][l]
                count += state[x*P+y+K][l] - state[x*P+y][l]
                count += state[K*P+L][l] - state[K*P+y+K][l] - state[x*P+L][l] + state[x*P+y+K][l]

                ans = max(ans, count)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Memory Limit Exceeded

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

def main():
    N, K = map(int, input().split())
    L = 2*K
    state = [[0, 0] for _ in range((L+1)**2)]

    for _ in range(N):
        x, y, c = map(str, input().split())
        if c == 'W':
            state[(int(x)%L+1)*(L+1)+int(y)%L+1][0] += 1
        else:
            state[(int(x)%L+1)*(L+1)+int(y)%L+1][1] += 1

    for i in range(L):
        for j in range(L):
            for k in [0, 1]:
                state[(i+1)*(L+1)+j+1][k] += state[(i+1)*(L+1)+j][k] + state[i*(L+1)+j+1][k] - state[i*(L+1)+j][k]

    P = L+1
    ans = 0
    for x in range(K):
        for y in range(K):
            for k in [0, 1]:
                count = 0
                count += state[x*P+y][k]
                count += state[(x+K)*P+y+K][k] - state[x*P+y+K][k] - state[(x+K)*P+y][k] + state[x*P+y][k]
                count += state[L*P+y][k] - state[(x+K)*P+y][k]
                count += state[x*P+L][k] - state[x*P+y+K][k]
                count += state[L*P+L][k] - state[(x+K)*P+L][k] - state[L*P+y+K][k] + state[(x+K)*P+y+K][k]

                l = k ^ 1
                count += state[(x+K)*P+y][l] - state[x*P+y][l]
                count += state[x*P+y+K][l] - state[x*P+y][l]
                count += state[L*P+y+K][l] - state[(x+K)*P+y+K][l] - state[L*P+y][l] + state[(x+K)*P+y][l]
                count += state[(x+K)*P+L][l] - state[(x+K)*P+y+K][l] - state[x*P+L][l] + state[x*P+y+K][l]

                ans = max(ans, count)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Memory Limit Exceeded

Solution code:
N,K = map(int,input().split())
XYC = [[int(x)%(2*K),int(y)%(2*K),int(c=="B")] for x,y,c in [input().split() for _ in [0]*N]]

score = [[[0]*(3*K) for _ in [0]*(3*K)] for _ in [0]*2]
for x,y,c in XYC:
    score[c][y][x] += 1
    if x<K: score[c][y][x+2*K] += 1
    if y<K: score[c][y+2*K][x] += 1
    if x<K and y<K: score[c][y+2*K][x+2*K] += 1

S = [[[0]*(3*K+1) for _ in [0]*(3*K+1)] for _ in [0]*2]
for c in range(2):
    for i in range(3*K):
        for j in range(3*K):
            S[c][i+1][j+1] = S[c][i][j+1] + score[c][i][j]
    for i in range(3*K):
        for j in range(3*K):
            S[c][i+1][j+1] += S[c][i+1][j]

def get_sum(c,si,sj,i,j):
    i+=1
    j+=1
    return S[c][i][j] + S[c][si][sj] - S[c][i][sj] - S[c][si][j]

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

Submission status: Memory Limit Exceeded

Solution code:
from subprocess import*
call(('julia','-e',"""
int(s)=parse(Int32,s)
intLine()=map(int,split(readline()))
function nextLine(k)
    x,y,c=split(readline())
    int(x)%2k+1,(int(y)+(c=="W")k)%2k+1
end
function solve(k,g)
    m=0
    for i=1:2k,j=1:2k
        a=0
        for x=-1:2,y=-1:2
            (x+y)%2!=0&&continue
            v,w=i+x*k,j+y*k
            v>0<w&&(a+=g[min(2k,v)][min(2k,w)])
            v>k&&w>0&&(a-=g[min(2k,v-k)][min(2k,w)])
            w>k&&v>0&&(a-=g[min(2k,v)][min(2k,w-k)])
            v>k<w&&(a+=g[min(2k,v-k)][min(2k,w-k)])
        end
        m=max(m,a)
    end
    m
end
function main()
    n,k=intLine()
    g=Array{Int32,1}[[0for j=1:2k]for i=1:2k]
    for i=1:n
        x,y=nextLine(k)
        g[x][y]+=1
    end
    println(solve(k,cumsum(map(cumsum,g))))
end
main()
"""))

Submission status: Memory Limit Exceeded

Solution code:
from subprocess import*
call(('julia','-e',"""
const lines=readlines()
input()=shift!(lines)
int(s)=parse(Int32,s)
intLine()=map(int,split(input()))
function nextLine(k)
    x,y,c=split(input())
    int(x)%2k+1,(int(y)+(c=="W")k)%2k+1
end
function solve(k,g)
    m=0
    for i=1:2k,j=1:2k
        a=0
        for x=-1:2,y=-1:2
            (x+y)%2!=0&&continue
            v,w=i+x*k,j+y*k
            v>0<w&&(a+=g[min(2k,v)][min(2k,w)])
            v>k&&w>0&&(a-=g[min(2k,v-k)][min(2k,w)])
            w>k&&v>0&&(a-=g[min(2k,v)][min(2k,w-k)])
            v>k<w&&(a+=g[min(2k,v-k)][min(2k,w-k)])
        end
        m=max(m,a)
    end
    m
end
function main()
    n,k=intLine()
    g=Array{Int32,1}[[0for j=1:2k]for i=1:2k]
    for i=1:n
        x,y=nextLine(k)
        g[x][y]+=1
    end
    println(solve(k,cumsum(map(cumsum,g))))
end
main()
"""))

Submission status: Memory Limit Exceeded

Solution code:
from subprocess import call
call(('julia','-e',"""
const lines=readlines()
input()=shift!(lines)
int(s)=parse(Int32,s)
intLine()=map(int,split(input()))
function nextLine(k)
    x,y,c=split(input())
    int(x)%2k+1,(int(y)+(c=="W")k)%2k+1
end
function solve(k,g)
    m=0
    for i=1:2k,j=1:2k
        a=0
        for x=-1:2,y=-1:2
            (x+y)%2!=0&&continue
            v,w=i+x*k,j+y*k
            v>0<w&&(a+=g[min(2k,v)][min(2k,w)])
            v>k&&w>0&&(a-=g[min(2k,v-k)][min(2k,w)])
            w>k&&v>0&&(a-=g[min(2k,v)][min(2k,w-k)])
            v>k<w&&(a+=g[min(2k,v-k)][min(2k,w-k)])
        end
        m=max(m,a)
    end
    m
end
function main()
    n,k=intLine()
    g=Array{Int32,1}[[0for j=1:2k]for i=1:2k]
    for i=1:n
        x,y=nextLine(k)
        g[x][y]+=1
    end
    println(solve(k,cumsum(map(cumsum,g))))
end
main()
"""))

Submission status: Memory Limit Exceeded

Solution code:
#(6,6)周期
#36種の希望

import numpy as np
N,K = map(int,input().split())
KK = 2*K
hope = np.zeros((KK,KK),dtype=np.int32)

XYC = [input().split() for _ in range(N)]

for x,y,c in XYC:
  x = int(x)
  y = int(y)
  if c == 'B':
    x -= K
  x %= KK
  y %= KK
  hope[x,y] += 1
# (x,y)を希望された場合、[x,x+K), [y,y+K)に終点があるべき
# 区間の重なってる枚数を集計。1,0,0,-1, cumsum
A = np.zeros((KK+K,KK+K),dtype=np.int64)
A[:-K,:-K] = hope[:]
A[K:,:-K] += -hope[:]
A[:-K,K:] += -hope[:]
A[K:,K:] += hope[:]
A = A.cumsum(axis = 0).cumsum(axis = 1)

# 実質同じ場所をまとめる
B = A[:,:KK]
B[:,:K] += A[:,KK:] #(3K,2K)
A = B[:KK,:]
A[:K,:] += B[KK:,:] #(2K,2K)
B = A[:K,:] #(K,2K)
B[:,:K] += A[K:,K:]
B[:,K:] += A[K:,:K]

answer = B.max()
print(answer)

Submission status: Memory Limit Exceeded

Solution code:
#(6,6)周期
#36種の希望

import numpy as np
N,K = map(int,input().split())
KK = 2*K
hope = np.zeros((KK,KK),dtype=np.int64)

XYC = [input().split() for _ in range(N)]

for x,y,c in XYC:
  x = int(x)
  y = int(y)
  if c == 'B':
    x -= K
  x %= KK
  y %= KK
  hope[x,y] += 1
# (x,y)を希望された場合、[x,x+K), [y,y+K)に終点があるべき
# 区間の重なってる枚数を集計。1,0,0,-1, cumsum
A = np.zeros((KK+K,KK+K),dtype=np.int64)
A[:-K,:-K] = hope[:]
A[K:,:-K] += -hope[:]
A[:-K,K:] += -hope[:]
A[K:,K:] += hope[:]
A = A.cumsum(axis = 0).cumsum(axis = 1)

# 実質同じ場所をまとめる
B = A[:,:KK]
B[:,:K] += A[:,KK:] #(3K,2K)
A = B[:KK,:]
A[:K,:] += B[KK:,:] #(2K,2K)
B = A[:K,:] #(K,2K)
B[:,:K] += A[K:,K:]
B[:,K:] += A[K:,:K]

answer = B.max()
print(answer)

Submission status: Memory Limit Exceeded

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

"""
参考：https://pitsbuffersolution.com/compro/atcoder/arc089d.php
　　　http://tutuz.hateblo.jp/entry/2018/06/20/212752
　　　https://paiza.hatenablog.com/entry/2014/05/28/%E3%82%82%E3%81%97%E5%A5%B3%E5%AD%90%E5%A4%A7%E7%94%9F%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9E%E3%81%AB%E3%80%8E%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%80%8F%E3%82%92%E5%9B%B3
　　　http://www.learning-algorithms.com/entry/2018/01/31/144519
　　　https://img.atcoder.jp/arc089/editorial.pdf
・2次元累積和
・0-indexedのまま行くか1-indexedにするか人によって色々で、
　それぞれに考慮する点があると思った。
・定数倍高速化のためループまとめて(4K^2)*3回を1回にしたから、
　5200万がO((4K)^2+(2K)^2)=2000万くらいになって結構速くなったはず。
"""

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

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

# K*2の正方形を右下まで動かすので、K*4まで作っておく
B = [[0] * (K*4+1) for i in range(K*4+1)]
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    # 白に塗る条件はxかyにKずらして黒の条件にする(これで2色考えなくていい)
    if c == 'W':
        y += K
    # 循環するのでmod K*2でやる
    # 累積和でひとつ前を見に行くので、1-indexedにする
    B[x%(K*2)+1][y%(K*2)+1] += 1

sm = [[0] * (K*4+1) for i in range(K*4+1)]
# 2次元累積和を取る
# 1-indexedなので、気にせず1からループすればいい
for i in range(1, K*4+1):
    for j in range(1, K*4+1):
        # K*2からはみ出る範囲も正しく累積和を出すため、K*2までの値を循環させる
        # 1-indexedにしているため、ここの加減がややこしい
        sm[i][j] = B[(i-1)%(K*2)+1][(j-1)%(K*2)+1]
        # 縦横の累積和を同時に集めていく
        sm[i][j] += sm[i][j-1] + sm[i-1][j] - sm[i-1][j-1]

# 2次元累積和に必要な4点の加減を行う
def get_sum(x1, y1, x2, y2, sm):
    # 1-indexedなので、x, yがマイナスの値になる考慮は必要ない
    res = sm[x2][y2] - sm[x1-1][y2] - sm[x2][y1-1] + sm[x1-1][y1-1]
    return res

ans = 0
for i in range(1, K*2+1):
    for j in range(1, K*2+1):
        # 1つ目の黒い正方形
        tmp = get_sum(i, j, i+K-1, j+K-1, sm)
        # 2つ目の黒い正方形
        tmp += get_sum(i+K, j+K, i+K*2-1, j+K*2-1, sm)
        ans = max(tmp, ans)
print(ans)

Submission status: Memory Limit Exceeded

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

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


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


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


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


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


def calc(x,y):
	return w[x][y]-w[x-K][y]-w[x][y+K]+w[x-K][y+K]

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

print ans

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
ans=[[0]*(3*k+10) for i in range(4*k+10)]
for i in range(n):
    x,y,c=input().split()
    x=int(x)
    y=int(y)
    a=x//k%2
    b=x%k
    d=y//k%2
    e=y%k
    x=b+a*k
    y=e+d*k
    if (a+d)%2==0:
        if c=="B":

            x=k-b
            y=k-e

        else:
            x=2*k-b
            y=k-e
    else:
        if c == "W":
            x = k - b
            y = k - e

        else:
            x = 2 * k - b
            y = k - e

    ans[x][y]+=1
    ans[x][y+k]-=1
    ans[x+k][y]-=1
    ans[x+k][y+k]+=1


for i in range(4*k+9):
    for j in range(3*k+9):
        ans[i][j+1]=ans[i][j]+ans[i][j+1]
for i in range(4*k+9):
    for j in range(3*k+9):
        ans[i+1][j]=ans[i][j]+ans[i+1][j]
anser=0

for x in range(k,2*k):
    for y in range(k,2*k):
        p=ans[x][y]+ans[x-k][y-k]+ans[x-k][y+k]+ans[x+k][y+k]+ans[x+k][y-k]
        anser=max(anser,p)
for x in range(2*k,3*k):
    for y in range(k,2*k):
        p = ans[x][y] + ans[x - k][y - k] + ans[x - k][y + k] + ans[x + k][y + k] + ans[x + k][y - k]+ans[x-2*k][y]
        anser = max(anser, p)
print(anser)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
ans=[[0]*(3*k+10) for i in range(4*k+10)]
for i in range(n):
    x,y,c=input().split()
    x=int(x)
    y=int(y)
    a=x//k%2
    b=x%k
    d=y//k%2
    e=y%k
    x=b+a*k
    y=e+d*k
    if (a+d)%2==0:
        if c=="B":

            x=k-b
            y=k-e

        else:
            x=2*k-b
            y=k-e
    else:
        if c == "W":
            x = k - b
            y = k - e

        else:
            x = 2 * k - b
            y = k - e

    ans[x][y]+=1
    ans[x][y+k]-=1
    ans[x+k][y]-=1
    ans[x+k][y+k]+=1


for i in range(4*k+9):
    for j in range(3*k+9):
        ans[i][j+1]=ans[i][j]+ans[i][j+1]
for i in range(4*k+9):
    for j in range(3*k+9):
        ans[i+1][j]=ans[i][j]+ans[i+1][j]
anser=0

for x in range(k,2*k):
    for y in range(k,2*k):
        p=ans[x][y]+ans[x-k][y-k]+ans[x-k][y+k]+ans[x+k][y+k]+ans[x+k][y-k]+ans[x+2*k][y]
        anser=max(anser,p)
for x in range(2*k,3*k):
    for y in range(k,2*k):
        p = ans[x][y] + ans[x - k][y - k] + ans[x - k][y + k] + ans[x + k][y + k] + ans[x + k][y - k]+ans[x-2*k][y]
        anser = max(anser, p)
print(anser)

Submission status: Accepted

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

ok = [ [0]*k for _ in range(k) ]
ng = [ [0]*k for _ in range(k) ]

ok_cnt = 0
ng_cnt = 0
for _ in range(n):
    x,y,c = map(str, input().split())
    x = int(x)%(k*2)
    y = int(y)%(k*2)
    if (x < k and y < k and c=='W') or (x >= k and y >= k and c=='W') or (x < k and y>= k and c =='B') or (x >= k and y < k and c =='B'):
        ok[x%k][y%k] += 1
        ok_cnt += 1
    else:
        ng[x%k][y%k] += 1
        ng_cnt += 1

ok_csums = [ [0]*(k+1) for _ in range(k+1)]
for i in range(k):
    for j in range(k):
        ok_csums[i+1][j+1] = ok_csums[i+1][j] + ok_csums[i][j+1] - ok_csums[i][j] + ok[i][j]

ng_csums = [ [0]*(k+1) for _ in range(k+1)]
for i in range(k):
    for j in range(k):
        ng_csums[i+1][j+1] = ng_csums[i+1][j] + ng_csums[i][j+1] - ng_csums[i][j] + ng[i][j]

    
ans = max(ok_cnt, ng_cnt)

# l u r b
for i in range(0,k+1):
    for j in range(0,k+1):
        ok_sum = ok_csums[i][j]
        ok_sum += (ok_csums[k][k] - ok_csums[i][k]- ok_csums[k][j] + ok_csums[i][j])
        ng_sum = ng_csums[i][k] - ng_csums[i][j]
        ng_sum += (ng_csums[k][j] - ng_csums[i][j])

        # ng_sum = 2*ng_cnt - ng_sum
        ans = max(ok_sum+ng_sum, ans)

for i in range(0,k+1):
    for j in range(0,k+1):
        ok_sum = ok_csums[i][k] - ok_csums[i][j]
        ok_sum += (ok_csums[k][j] - ok_csums[i][j])
        ng_sum = ng_csums[i][j]
        ng_sum += (ng_csums[k][k] - ng_csums[i][k]- ng_csums[k][j] + ng_csums[i][j])
        # ng_sum -= 2*ng_cnt
        # ng_sum = 2*ng_cnt - ng_sum
        ans = max(ok_sum+ng_sum, ans)


# # l u
# for i in range(1,k+1):
#     for j in range(1,k+1):
#         ok_sum = ok_csums[i][j]
#         ng_sum = ng_cnt - ng_csums[i][j]
#         ans = max(ok_sum+ng_sum, ans)

# # r b
# for i in range(0,k):
#     for j in range(0,k):
#         ok_sum = ok_csums[k][k] - ok_csums[i][k]-ok_csums[k][j] + ok_csums[i][j]
#         ng_sum = ng_cnt - (ng_csums[k][k] - ng_csums[i][k]-ng_csums[k][j] + ng_csums[i][j])
#         ans = max(ok_sum+ng_sum, ans)

# # l b
# for i in range(0,k):
#     for j in range(1,k+1):
#         ok_sum = ok_csums[k][j] - ok_csums[i][j]
#         ng_sum = ng_cnt - (ng_csums[k][j] - ng_csums[i][j])
#         ans = max(ok_sum+ng_sum, ans)


# # r u
# for i in range(1,k+1):
#     for j in range(0,k):
#         ok_sum = ok_csums[i][k] - ok_csums[i][j]
#         ng_sum = ng_cnt - (ng_csums[i][k] - ng_csums[i][j])
#         ans = max(ok_sum+ng_sum, ans)


print(ans)

Submission status: Accepted

Solution code:
# 2K * 2Kの正方形で一周するので、
# (X,Y) -> (X % 2K, Y % 2K)に言い換えることが出来る
# Wの表とBの表を別々で持つ
# それぞれの表で二次元累積和を持ち、範囲に対する得点を求められるようにする
# K * Kの正方形の左下隅を1000 * 1000通り全探索して最大値を求める
# 効率化のため、上記K * Kの正方形が黒である場合と白である場合を同時に計算する
# その領域で見つけた白の個数は、黒を計算するときは「白の総数 - 見つけた白の個数」とすることで白の得点として加算できるえ

import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
white = [[0] * (2 * K + 1) for i in range(2 * K + 1)]
black = [[0] * (2 * K + 1) for i in range(2 * K + 1)]
# 黒を数えるときは、同時に白を数えて、白全体の数から引く
white_all = 0
black_all = 0
for i in range(N):
  x,y,c = readline().split()
  x,y = int(x) % (2 * K),int(y) % (2 * K)
  if c == "W":
    white[x + 1][y + 1] += 1
    white_all += 1
  else:
    black[x + 1][y + 1] += 1
    black_all += 1
  
for i in range(1, len(white)):
  for j in range(1, len(white[i])):
    white[i][j] += white[i][j - 1]
    
for j in range(1, len(white)):
  for i in range(1, len(white[j])):
    white[i][j] += white[i - 1][j]

for i in range(1, len(black)):
  for j in range(1, len(black[i])):
    black[i][j] += black[i][j - 1]
    
for j in range(1, len(black)):
  for i in range(1, len(black[j])):
    black[i][j] += black[i - 1][j]

cases = ((0,0),(K,K),(-K,-K),(K,-K),(-K,K))
ans = 0
  
for i in range(1, K + 1):
  for j in range(1, K + 1):
    # 基本となる正方形の左下隅・右上は以下の通り
    # (i,j),(i + K - 1, j + K - 1)
    # これに対して、
    # i,jともに +Kしたもの
    # i,jともに -Kしたもの
    # iは+K,jは-Kしたもの
    # iは-K,jは+Kしたもの
    # が考えられる範囲となる
    # なお、最小値は1,1、最大値は2 * K,2 * Kとなる
    # iだけ+Kした正方形は、その正方形の白黒を反転させると計上済みとなる
    black_cnt = 0
    white_cnt = 0
    for c in cases:
      x1 = i + c[0]
      y1 = j + c[1]
      x2 = x1 + K - 1
      y2 = y1 + K - 1
        
      x1 = max(1, x1)
      y1 = max(1, y1)
      x2 = min(2 * K, x2)
      y2 = min(2 * K, y2)
      if x1 > x2 or y1 > y2:
        continue
        
      # その領域の黒と白の数を数える
      black_cnt += black[x2][y2] - black[x2][y1 - 1] - black[x1 - 1][y2] + black[x1 - 1][y1 - 1]
      white_cnt += white[x2][y2] - white[x2][y1 - 1] - white[x1 - 1][y2] + white[x1 - 1][y1 - 1]
      
    # その正方形が黒の場合と白の場合を両方算出し、比較する
    point = max(black_cnt + (white_all - white_cnt),white_cnt + (black_all - black_cnt))
    if ans < point:
      ans = point
    
print(ans)

Submission status: Accepted

Solution code:
# 2K * 2Kの正方形で一周するので、
# (X,Y) -> (X % 2K, Y % 2K)に言い換えることが出来る
# Wの表とBの表を別々で持つ
# それぞれの表で二次元累積和を持ち、範囲に対する得点を求められるようにする
# K * Kの正方形の左下隅を1000 * 1000通り全探索して最大値を求める
# 効率化のため、上記K * Kの正方形が黒である場合と白である場合を同時に計算する
# その領域で見つけた白の個数は、黒を計算するときは「白の総数 - 見つけた白の個数」とすることで白の得点として加算できるえ

import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
white = [[0] * (2 * K + 1) for i in range(2 * K + 1)]
black = [[0] * (2 * K + 1) for i in range(2 * K + 1)]
# 黒を数えるときは、同時に白を数えて、白全体の数から引く
white_all = 0
black_all = 0
for i in range(N):
  x,y,c = readline().split()
  x,y = int(x) % (2 * K),int(y) % (2 * K)
  if c == "W":
    white[x + 1][y + 1] += 1
    white_all += 1
  else:
    black[x + 1][y + 1] += 1
    black_all += 1
  
for i in range(1, len(white)):
  for j in range(1, len(white[i])):
    white[i][j] += white[i][j - 1]
    
for j in range(1, len(white)):
  for i in range(1, len(white[j])):
    white[i][j] += white[i - 1][j]

for i in range(1, len(black)):
  for j in range(1, len(black[i])):
    black[i][j] += black[i][j - 1]
    
for j in range(1, len(black)):
  for i in range(1, len(black[j])):
    black[i][j] += black[i - 1][j]

cases = ((0,0),(K,K),(-K,-K),(K,-K),(-K,K))
ans = 0
  
for i in range(1, K + 1):
  for j in range(1, K + 1):
    # 基本となる黒の正方形の左下隅・右上は以下の通り
    # (i,j),(i + K - 1, j + K - 1)
    # これに対して、
    # i,jともに +Kしたもの
    # i,jともに -Kしたもの
    # iは+K,jは-Kしたもの
    # iは-K,jは+Kしたもの
    # が考えられる範囲となる
    # なお、最小値は1,1、最大値は2 * K,2 * Kとなる
    black_cnt = 0
    white_cnt = 0
    for c in cases:
      x1 = i + c[0]
      y1 = j + c[1]
      x2 = x1 + K - 1
      y2 = y1 + K - 1
        
      x1 = max(1, x1)
      y1 = max(1, y1)
      x2 = min(2 * K, x2)
      y2 = min(2 * K, y2)
      if x1 > x2 or y1 > y2:
        continue
        
      # その領域の黒と白の数を数える
      black_cnt += black[x2][y2] - black[x2][y1 - 1] - black[x1 - 1][y2] + black[x1 - 1][y1 - 1]
      white_cnt += white[x2][y2] - white[x2][y1 - 1] - white[x1 - 1][y2] + white[x1 - 1][y1 - 1]
      
    # その正方形が黒の場合と白の場合を両方足し合わせる
    point = max(black_cnt + (white_all - white_cnt),white_cnt + (black_all - black_cnt))
    if ans < point:
      ans = point
    
print(ans)