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:
#!usr/bim/python
#! -*- coding: utf-8 -*-

n,k = map(int,raw_input().split())
kibou = []
for i in range(n):
    line = raw_input().split()
    line[0] = int(line[0])
    line[1] = int(line[1])
    if line[2] == "W":
        line[2] = 0
    else:
        line[2] = 1
    kibou.append(line)

max_score = 0
for i in range(k):
    for j in range(k):
        score = 0
        for line in kibou:
            if ((line[0]+i)/k+(line[1]+j)/k)%2 == line[2]:
                score += 1
        max_score = max(score,max_score,(n-score))
        if max_score == n:
            break

print max_score

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))
x = []
y = []
c = []
for i in range(N):
    temp = list(input().split())
    x.append(int(temp[0]))
    y.append(int(temp[1]))
    c.append(temp[2])

result = 0
flag = True
for k in [['B', 'W'], ['W', 'B']]:
    if flag:
        for i in range(K + 1):
            if flag:
                for j in range(K + 1):
                    count = 0
                    for n in range(N):
                        xp = int(((x[n] + i) % (2 * K)) / K)
                        yp = int(((y[n] + j) % (2 * K)) / K)
                        if xp + yp in [0, 2] and c[n] == k[0]:
                            count += 1
                        elif xp + yp == 1 and c[n] == k[1]:
                            count += 1
                    if result < count:
                        result = count
                    if result == N:
                        flag = False
                        break

print(result)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

n,k = map(int,raw_input().split())
kibou = []
for i in range(n):
    line = raw_input().split()
    line[0] = int(line[0])
    line[1] = int(line[1])
    if line[2] == "W":
        line[2] = 0
    else:
        line[2] = 1
    kibou.append(line)

max_score = 0
for i in range(k):
    for j in range(k):
        for color in range(2):
            score = 0
            for line in kibou:
                if ((line[0]+i)/k+(line[1]+j)/k+color)%2 == line[2]:
                    #print "o",
                    score += 1
                #else:
                #    print "x",
            #print score
            max_score = max(score,max_score)

print max_score

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, k = map(int, input().split())
k2 = k * 2
requires = defaultdict(lambda: [0, 0])
for i in range(n):
    x, y, c = input().split()
    x, y = int(x), int(y)
    rx, ry = x % k2, y % k2
    b = c == 'B'
    if rx > k:
        if ry > k:
            rx -= k
            ry -= k
        else:
            rx -= k
            b = not b

    requires[rx, ry][b] += 1

ans = 0
for dx in range(k):
    for dy in range(k):
        cnt_w, cnt_b = 0, 0
        for (x, y), (w, b) in requires.items():
            f = ((x + dx) // k + (y + dy) // k) & 1
            if f:
                cnt_w += b
                cnt_b += w
            else:
                cnt_w += w
                cnt_b += b
        ans = max(ans, cnt_b, cnt_w)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
x = []
y = []
c = []

for i in range(n):
    x_, y_, c_ = input().split()
    x.append(int(x_))
    y.append(int(y_))
    if c_ == 'W':
        c.append(0)
    else:
        c.append(1)

import math
def solve():
    max_n_desire = 0

    for kx in range(k):
        for ky in range(k):
            n_desire = 0
            for i in range(n):
                x_ = x[i] - kx
                y_ = y[i] - ky
                ca = (math.ceil(x_ / k) + math.ceil(y_ / k)) % 2
                if ca == c[i]:
                    n_desire += 1

            n_desire = max(n_desire, n-n_desire)
            max_n_desire = max(max_n_desire, n_desire)

    print(max_n_desire)

solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, k = map(int, input().split())
k2 = k * 2
requires = defaultdict(lambda: [0, 0])
for i in range(n):
    x, y, c = input().split()
    x, y = int(x), int(y)
    requires[x % k2, y % k2][c == 'B'] += 1

ans = 0
for dx in range(k):
    for dy in range(k):
        cnt_w, cnt_b = 0, 0
        for (x, y), (w, b) in requires.items():
            f = ((x + dx) // k + (y + dy) // k) & 1
            if f:
                cnt_w += b
                cnt_b += w
            else:
                cnt_w += w
                cnt_b += b
        ans = max(ans, cnt_b, cnt_w)
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    black = defaultdict(int)
    white = defaultdict(int)
    for _ in range(N):
        x, y, c = input().split()
        x = int(x)
        y = int(y)
        if c == 'B':
            x_, y_ = x % (2*K), y % (2*K)
            if x_ < K and y_ < K:
                black[(x_, y_)] += 1
            elif x_ >= K and y_ < K:
                white[(x_ - K, y_)] += 1
            elif x_ < K and y_ >= K:
                white[(x_, y_ - K)] += 1
            else:
                black[(x_ - K, y_ - K)] += 1
        else:
            x_, y_ = x % (2 * K), y % (2 * K)
            if x_ < K and y_ < K:
                white[(x_, y_)] += 1
            elif x_ >= K and y_ < K:
                black[(x_ - K, y_)] += 1
            elif x_ < K and y_ >= K:
                black[(x_, y_ - K)] += 1
            else:
                white[(x_ - K, y_ - K)] += 1

    cs_b = [[0] * (K+1) for _ in range(K+1)]
    cs_w = [[0] * (K+1) for _ in range(K+1)]
    for i in range(K):
        for j in range(K):
            cs_b[i+1][j+1] = cs_b[i+1][j] + cs_b[i][j+1] - cs_b[i][j] + black[(i, j)]
            cs_w[i + 1][j + 1] = cs_w[i + 1][j] + cs_w[i][j + 1] - cs_w[i][j] + white[(i, j)]

    ans = 0
    for i in range(K):
        for j in range(K):
            ans_b = cs_b[i][j] + cs_b[-1][-1] - cs_b[-1][j] - cs_b[i][-1] + cs_b[i][j]
            ans_w = cs_w[i][-1] - cs_w[i][j] + cs_w[-1][j] - cs_w[i][j]
            ans_w2 = cs_w[i][j] + cs_w[-1][-1] - cs_w[-1][j] - cs_w[i][-1] + cs_w[i][j]
            ans_b2 = cs_b[i][-1] - cs_b[i][j] + cs_b[-1][j] - cs_b[i][j]
            ans = max(ans, ans_b + ans_w, ans_b2 + ans_w2)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Memory Limit Exceeded

Solution code:
n,k = map(int,input().split())
dpb = [[0]*(4*k+1) for i in range(4*k+1)]
dpw = [[0]*(4*k+1) for i in range(4*k+1)]
for i in range(n):
  x,y,c = map(str,input().split())
  x = int(x)
  y = int(y)
  if c == "W":
    dpw[x%(2*k)+1][y%(2*k)+1] += 1
    dpw[x%(2*k)+2*k+1][y%(2*k)+2*k+1] += 1
    dpw[x%(2*k)+2*k+1][y%(2*k)+1] += 1
    dpw[x%(2*k)+1][y%(2*k)+2*k+1] += 1
  else:
    dpb[x%(2*k)+1][y%(2*k)+1] += 1
    dpb[x%(2*k)+2*k+1][y%(2*k)+2*k+1] += 1
    dpb[x%(2*k)+2*k+1][y%(2*k)+1] += 1
    dpb[x%(2*k)+1][y%(2*k)+2*k+1] += 1
for i in range(1,4*k+1):
  for j in range(1,4*k+1):
    dpw[i][j] += dpw[i-1][j] + dpw[i][j-1]-dpw[i-1][j-1]
    dpb[i][j] += dpb[i-1][j] + dpb[i][j-1]-dpb[i-1][j-1]
ans = 0
for i in range(1,2*k+1):
  for j in range(1,2*k+1):
    tmp = 0
    tmp += dpw[k+i-1][k+j-1]+dpw[i-1][j-1]-dpw[i-1][j+k-1]-dpw[i+k-1][j-1]
    tmp += dpw[k+i-1+k][k+j-1+k]+dpw[i-1+k][j-1+k]-dpw[i-1+k][j+k-1+k]-dpw[i+k-1+k][j-1+k]
    tmp += dpb[k+i-1+k][k+j-1]+dpb[i-1+k][j-1]-dpb[i-1+k][j+k-1]-dpb[i+k-1+k][j-1]
    tmp += dpb[k+i-1][k+j-1+k]+dpb[i-1][j-1+k]-dpb[i-1][j+k-1+k]-dpb[i+k-1][j-1+k]
    ans = max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

n,k = map(int,readline().split())
data = [i.split() for i in readlines()]

cumsum_w = [[0] * (k+1) for _ in range(k+1)]
cumsum_b = [[0] * (k+1) for _ in range(k+1)]
for x,y,c in data:
    x = int(x)
    y = int(y)
    c = 0 if (c=='W') else 1
    c += x//k + y//k
    c %= 2
    x %= k
    y %= k
    if(c==0):
        cumsum_w[x][y] += 1
    else:
        cumsum_b[x][y] += 1

for i in range(k):
    for j in range(1,k):
        cumsum_w[i][j] += cumsum_w[i][j-1]
        cumsum_b[i][j] += cumsum_b[i][j-1]

for i in range(1,k):
    for j in range(k):
        cumsum_w[i][j] += cumsum_w[i-1][j]
        cumsum_b[i][j] += cumsum_b[i-1][j]

ans = 0
for x in range(k):
    for y in range(k):
        tmp = (cumsum_w[k-1][k-1]
                - cumsum_w[x-1][k-1]
                - cumsum_w[k-1][y-1]
                + 2 * cumsum_w[x-1][y-1]
                + cumsum_b[x-1][k-1]
                + cumsum_b[k-1][y-1]
                - 2 * cumsum_b[x-1][y-1])
        ans = max(ans,tmp)

        tmp = (cumsum_b[k-1][k-1]
                - cumsum_b[x-1][k-1]
                - cumsum_b[k-1][y-1]
                + 2 * cumsum_b[x-1][y-1]
                + cumsum_w[x-1][k-1]
                + cumsum_w[k-1][y-1]
                - 2 * cumsum_w[x-1][y-1])
        ans = max(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
from pprint import *
N,K=map(int,input().split())
dpw=[[0 for _ in range(2*K+1)] for _ in range(2*K+1)]
dpb=[[0 for _ in range(2*K+1)] for _ in range(2*K+1)]
def getmatnum(x1,y1,x2,y2,mat):#左上を(x1,y1)右下を(x2,y2)にしてmatの中の左上~右下の領域の和をdpから算出
    if (x2==0)or(y2==0):
        return 0
    else:
        if (x1==-1):
            x1=0
        if (y1==-1):
            y1=0
        return mat[y2][x2]-mat[y1][x2]-mat[y2][x1]+mat[y1][x1]








for i in range(N):
    x,y,c=input().split()
    x=int(x)
    y=int(y)
    #print(x,y,c)
    if c=="W":
        dpw[(y%(2*K))+1][(x%(2*K))+1]=dpw[(y%(2*K))+1][(x%(2*K))+1]+1
    else:
        dpb[(y % (2*K))+1][(x % (2*K))+1] = dpb[(y % (2*K))+1][(x % (2*K))+1] + 1
#pprint(dpw)
#pprint(dpb)

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

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

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

for i in range(1,2*K+1):
    for j in range(1,2*K+1):
        dpw[i][j]=dpw[i-1][j]+dpw[i][j]
ans=0
for i in range(K):
    for j in range(K):
        k=i+K
        l=j+K
        b1=getmatnum(-1,-1,i,j,dpb)+getmatnum(k,-1,2*K,j,dpb)+getmatnum(i,j,k,l,dpb)+getmatnum(-1,l,i,2*K,dpb)+getmatnum(k,l,2*K,2*K,dpb)
        w1=getmatnum(i,-1,k,j,dpw)+getmatnum(-1,j,i,l,dpw)+getmatnum(k,j,2*K,l,dpw)+getmatnum(i,l,k,2*K,dpw)
        b2=getmatnum(-1,-1,i,j,dpw)+getmatnum(k,-1,2*K,j,dpw)+getmatnum(i,j,k,l,dpw)+getmatnum(-1,l,i,2*K,dpw)+getmatnum(k,l,2*K,2*K,dpw)
        w2=getmatnum(i,-1,k,j,dpb)+getmatnum(-1,j,i,l,dpb)+getmatnum(k,j,2*K,l,dpb)+getmatnum(i,l,k,2*K,dpb)
        ans=max(ans,b1+w1,b2+w2)

        #print(i,j,k,l)
print(ans)
        #
#pprint(dpw)
#pprint(dpb)

Submission status: Accepted

Solution code:
class cumsum2D:
    def __init__(self, data):
        self.N = len(data)
        self.M= len(data[0])
        self.cum = [[0] * (self.M + 1) for _ in range(self.N + 1)]
        for i in range(self.N):
            for j in range(self.M):
                self.cum[i + 1][j + 1] = self.cum[i][j + 1] + self.cum[i + 1][j] - self.cum[i][j] + data[i][j]

    def get(self,x1,y1,x2,y2):
        """
        長方形の領域 [x1,x2)*[y1,y2) の範囲内にインプットされた数字の和を取る
        """
        return self.cum[x2][y2] - self.cum[x1][y2] - self.cum[x2][y1] + self.cum[x1][y1]

########################################################################################################
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
B = [[0]*(2*K) for _ in range(2*K)]
W = [[0]*(2*K) for _ in range(2*K)]
for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c=="B":
        B[x%(2*K)][y%(2*K)] += 1
    else:
        W[x%(2*K)][y%(2*K)] += 1
cumB, cumW = cumsum2D(B), cumsum2D(W)
res = 0
for i in range(K+1):
    for j in range(K+1):
        res = max(cumW.get(0,0,i,j) + cumW.get(i,j,i+K,j+K) + cumW.get(i+K,j+K,2*K,2*K) + cumW.get(i+K,0,2*K,j) + cumW.get(0,j+K,i,2*K) + cumB.get(i,0,i+K,j) + cumB.get(0,j,i,j+K) + cumB.get(i+K,j,2*K,j+K) + cumB.get(i,j+K,i+K,2*K), cumB.get(0,0,i,j) + cumB.get(i,j,i+K,j+K) + cumB.get(i+K,j+K,2*K,2*K) + cumB.get(i+K,0,2*K,j) + cumB.get(0,j+K,i,2*K) + cumW.get(i,0,i+K,j) + cumW.get(0,j,i,j+K) + cumW.get(i+K,j,2*K,j+K) + cumW.get(i,j+K,i+K,2*K), res)
print(res)

Submission status: Accepted

Solution code:
from numpy import*;N,K=map(int,input().split());m,L,o=zeros((3*K,3*K)),2*K,0
for _ in[0]*N:x,y,c=input().split();t=c=='W';m[int(x)%L,int(y)%L]+=2*t-1;o+=t
for _ in"00":m[L:]=m[:K];m=cumsum(m,0);m[:L]-=m[K:];m=m.T
m=m[:L,:L];print(o-int((m+roll(roll(m,K,0),K,1)).min()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections,math,fractions
sys.setrecursionlimit(1000000)
INF = float("inf")

N,K = map(int,sys.stdin.readline().split())
xyc = tuple(tuple(sys.stdin.readline().rstrip().split()) for _ in range(N)) # multi line with multi param
xyc = tuple((int(x)%(2*K),int(y)%(2*K),c=="W")for x,y,c in xyc)
W = K
H = K
grid_w = [[0]*(W) for _ in range(H)]
grid_b = [[0]*(W) for _ in range(H)]

for x,y,c in xyc:
    r = (x//K+y//K)%2 # reverse or not
    c = c ^ r
    if c:
        grid_w[y%K][x%K] += 1
    else:
        grid_b[y%K][x%K] += 1
# 4 3
# 0 1 W
# 1 2 W
# 5 3 B
# 5 4 B

# 6 2
# 1 2 B
# 2 1 W
# 2 2 B
# 1 0 B
# 0 6 W
# 4 5 W
white =  [[0]*(W+1) for _ in range(H+1)]
black =  [[0]*(W+1) for _ in range(H+1)]
for r in range(H):
    for c in range(W):
        black[r+1][c+1] = black[r+1][c]+grid_b[r][c]
        white[r+1][c+1] = white[r+1][c]+grid_w[r][c]
for r in range(H):
    for c in range(W+1):
        black[r+1][c] += black[r][c]
        white[r+1][c] += white[r][c]
#print(grid_b,grid_w)
#print(black,white)
ret = 0
for r in range(K+1):
    for c in range(K+1):
        b = black[H][W]-black[H][c]-black[r][W]+2*black[r][c]
        w = white[H][c]+white[r][W]-2*white[r][c]
        #print(r,c,b,w)
        ret = max(ret,b+w)
        b = black[H][c]+black[r][W]-2*black[r][c]
        w = white[H][W]-white[H][c]-white[r][W]+2*white[r][c]
        #print(r,c,b,w)
        ret = max(ret,b+w)

print(ret)

Submission status: Accepted

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

Bcnt = [[0 for j in range(K+1)] for i in range(K+1)]
Wcnt = [[0 for j in range(K+1)] for i in range(K+1)]

for i in range(N):
    x,y,c = input().split()
    x,y = int(x),int(y)
    if ((x-x%K)/K + (y-y%K)/K)%2:
        if c == 'W':
            Bcnt[x%K+1][y%K+1] += 1
        else:
            Wcnt[x%K+1][y%K+1] += 1
    else:
        if c == 'W':
            Wcnt[x%K+1][y%K+1] += 1
        else:
            Bcnt[x%K+1][y%K+1] += 1

for i in range(K):
    for j in range(K):
        Bcnt[i+1][j+1] += Bcnt[i+1][j] + Bcnt[i][j+1] - Bcnt[i][j]
        Wcnt[i+1][j+1] += Wcnt[i+1][j] + Wcnt[i][j+1] - Wcnt[i][j]

ans = 0
Bs = Bcnt[K][K]
Ws = Wcnt[K][K]

for i in range(K+1):
    for j in range(K+1):
        B = Bcnt[K][K] - Bcnt[K][j] - Bcnt[i][K] + 2*Bcnt[i][j]
        W = Wcnt[K][K] - Wcnt[K][j] - Wcnt[i][K] + 2*Wcnt[i][j]
        ans = max(ans, B+Ws-W, W+Bs-B)

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
table=[[0]*K for i in range(K)]#W=1
C=0
for i in range(N):
    x,y,z=input().split()
    x = int(x)
    y=int(y)
    if z=='B':
        y +=K
    x %=(2*K)
    y %=(2*K)
    t = (x//K +y//K)%2
    x%= K
    y%=K
    if t:
        table[y][x]-=1
    else:
        table[y][x]+=1
        C+=1
B=N-C
#print(table)
pr=[[0]*(K+1) for i in range(K)]
for i in range(K):
    for j in range(K):
        pr[j][i+1]=pr[j][i]+table[j][i]
#print(pr)
pr2=[[0]*(K+1) for i in range(K+1)]
for j in range(K):
    for i in range(K):
        pr2[j+1][i+1]=pr2[j][i+1]+pr[j][i+1]
#print(pr2)
ans = 0
for i in range(K+1):
    for j in range(K+1):
        #s=pr2[K][K]-pr2[i-1][K] -pr2[K][j-1]+2*pr2[i-1][j-1]
        s =pr2[i][K] +pr2[K][j]-2*pr2[i][j]
        #白で塗った時に差し引き難点もらえるか
        #t=pr2[K][K]-s#黒で塗る
        #print(s,t,s-t,C-s)
        ans = max(ans,C-s,B+s)
print(ans)

Submission status: Accepted

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

amat_white,amat_black=[],[]
for i in range(2*K):
  amat_white.append([0]*(2*K))
  amat_black.append([0]*(2*K))

smat_white,smat_black=[],[]
for i in range(2*K+1):  
  smat_white.append([0]*(2*K+1))
  smat_black.append([0]*(2*K+1))

num_white,num_black=0,0
for i in range(N):
  x,y,c=input().split()  
  xx=int(x)%(2*K)
  yy=int(y)%(2*K)
  
  if xx<K and yy<K:
    if c=="W":
      amat_white[xx][yy]+=1
      amat_white[xx+K][yy+K]+=1
      num_white+=1
    else:
      amat_black[xx][yy]+=1
      amat_black[xx+K][yy+K]+=1
      num_black+=1
  elif xx>=K and yy>=K:
    if c=="W":
      amat_white[xx-K][yy-K]+=1
      amat_white[xx][yy]+=1
      num_white+=1
    else:
      amat_black[xx-K][yy-K]+=1
      amat_black[xx][yy]+=1
      num_black+=1
  elif xx<K and yy>=K:
    if c=="W":
      amat_black[xx][yy-K]+=1
      amat_black[xx+K][yy]+=1
      num_black+=1
    else:
      amat_white[xx][yy-K]+=1
      amat_white[xx+K][yy]+=1
      num_white+=1
  elif xx>=K and yy<K:
    if c=="W":
      amat_black[xx-K][yy]+=1
      amat_black[xx][yy+K]+=1
      num_black+=1
    else:
      amat_white[xx-K][yy]+=1
      amat_white[xx][yy+K]+=1
      num_white+=1
  else:
    None
#print(amat_white)
#print(amat_black)

for i in range(1,2*K+1):
  for j in range(1,2*K+1):
    smat_white[i][j]=amat_white[i-1][j-1]+smat_white[i][j-1]+smat_white[i-1][j]-smat_white[i-1][j-1]
    smat_black[i][j]=amat_black[i-1][j-1]+smat_black[i][j-1]+smat_black[i-1][j]-smat_black[i-1][j-1]
#print(smat_white)
#print(smat_black)

max_answer=0
#white
for i in range(K):
  for j in range(K):
    answer_white=smat_white[i+K][j+K]-smat_white[i][j+K]-smat_white[i+K][j]+smat_white[i][j]
    answer_black=num_black-(smat_black[i+K][j+K]-smat_black[i][j+K]-smat_black[i+K][j]+smat_black[i][j])
    max_answer=max(max_answer,(answer_white+answer_black))
    #print(i,j,answer_white,answer_black)
#black
for i in range(K):
  for j in range(K):
    answer_white=num_white-(smat_white[i+K][j+K]-smat_white[i][j+K]-smat_white[i+K][j]+smat_white[i][j])
    answer_black=smat_black[i+K][j+K]-smat_black[i][j+K]-smat_black[i+K][j]+smat_black[i][j]
    max_answer=max(max_answer,(answer_white+answer_black))
    #print(i,j,answer_white,answer_black)
    
print(max_answer)

Submission status: Accepted

Solution code:
import numpy as np
n,k=map(int,input().split())
m=np.zeros((3*k,3*k),dtype=int)
l=2*k
o=0
for _ in range(n):
  x,y,c=input().split()
  x,y=int(x)%l,int(y)%l
  t=c=='W'
  m[x,y]+=1-2*t
  o+=t
for _ in range(2):
  m[l:]=m[:k]
  m=np.cumsum(m,axis=0)
  m[:l]=m[k:]-m[:l]
  m=m.T
m=m[:l,:l]
print(o+(m+np.roll(np.roll(m,k,axis=0),k,axis=1)).max())

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
B = [[0]*(2*K+1) for  _ in range(2*K+1)]
B2 = [[0]*(2*K+1) for  _ in range(2*K+1)]
for _ in range(N):
    a, b, c = input().strip().split()
    a, b, c = int(a), int(b), 1 if c == 'B' else 0
    x, y = (a+K*c)%(2*K), b%(2*K)
    if x > K-1 and y > K-1:
        x, y = x-K, y-K
    if x < K and y > K-1:
        x, y = x+K, y-K
    B[x+1][y+1] += 1
    B2[(x+K)%(2*K)+1][y+1] += 1
R = [[0]*(2*K+1) for  _ in range(2*K+1)]
R2 = [[0]*(2*K+1) for  _ in range(2*K+1)]
for i in range(1, 2*K+1):
    for j in range(1, 2*K+1):
        R[i][j] = R[i-1][j] + R[i][j-1] - R[i-1][j-1] + B[i][j]
        R2[i][j] = R2[i-1][j] + R2[i][j-1] - R2[i-1][j-1] + B2[i][j]
r = 0
for i in range(K):
    for j in range(K):
        t1 = R[2*K][j] + R[i+K][K] - R[i][K] - 2*R[i+K][j] + 2*R[i][j]
        r = max(r, t1)
        t1 = R2[2*K][j] + R2[i+K][K] - R2[i][K] - 2*R2[i+K][j] + 2*R2[i][j]
        r = max(r, t1)
print(r)

Submission status: Accepted

Solution code:
def f(i, j):
    i1, j1 = i, j
    if i1 > 2*K:
        return 0
    if j1 > 2*K:
        return 0
    i2, j2 = min(i+K, 2*K), min(j+K, 2*K)
    if i < 0:
        if j < 0:
            r = R[i2][j2]
        else:
            r = R[i2][j2] - R[i2][j1]
    elif j<0:
        r = R[i2][j2] - R[i1][j2]
    else:
#        print(i1,j1,i2,j2)
        r = R[i2][j2] - R[i1][j2] - R[i2][j1] + R[i1][j1]
    return r

N, K = map(int, input().split())
B = [[0]*(2*K+1) for  _ in range(2*K+1)]
for _ in range(N):
    a, b, c = input().strip().split()
    a, b, c = int(a), int(b), 1 if c == 'W' else 0
    B[(a+K*c)%(2*K)+1][b%(2*K)+1] += 1
R = [[0]*(2*K+1) for  _ in range(2*K+1)]
for i in range(1, 2*K+1):
    for j in range(1, 2*K+1):
        R[i][j] = R[i-1][j] + R[i][j-1] - R[i-1][j-1] + B[i][j]
r = 0
for i in range(K):
    for j in range(K):
        t = f(i,j)+f(i-K, j-K)+f(i+K, j+K)+f(i-K, j+K)+f(i+K, j-K)
#        print(i,j, f(i,j),f(i-K, j-K),f(i+K, j+K),f(i-K, j+K),f(i-K, j+K))
#        print(i, j, t, f(i-K,j))
        r = max(r, t)
#        print(i, j, t0,t1,t2)
for i in range(K):
    for j in range(K):
        i += K
        t = f(i,j)+f(i-K, j-K)+f(i-K, j+K)+f(i-2*K, j)
        r = max(r, t)
for i in range(K):
    for j in range(K):
        j += K
        t = f(i,j)+f(i-K, j-K)+f(i+K, j-K)+f(i, j-2*K)
        r = max(r, t)
print(r)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    black = defaultdict(int)
    white = defaultdict(int)
    for _ in range(N):
        x, y, c = input().split()
        x = int(x)
        y = int(y)
        if c == 'B':
            x_, y_ = x % (2*K), y % (2*K)
            if x_ < K and y_ < K:
                black[x_ * K + y_] += 1
            elif x_ >= K and y_ < K:
                white[(x_ - K) *K +y_] += 1
            elif x_ < K and y_ >= K:
                white[x_ * K + y_ - K] += 1
            else:
                black[(x_ - K)*K + y_ - K] += 1
        else:
            x_, y_ = x % (2 * K), y % (2 * K)
            if x_ < K and y_ < K:
                white[x_*K + y_] += 1
            elif x_ >= K and y_ < K:
                black[(x_ - K)*K + y_] += 1
            elif x_ < K and y_ >= K:
                black[x_*K+ y_ - K] += 1
            else:
                white[(x_ - K)*K + y_ - K] += 1

    cs_b = [[0] * (K+1) for _ in range(K+1)]
    cs_w = [[0] * (K+1) for _ in range(K+1)]
    for i in range(K):
        for j in range(K):
            cs_b[i+1][j+1] = cs_b[i+1][j] + cs_b[i][j+1] - cs_b[i][j] + black[i*K+j]
            cs_w[i + 1][j + 1] = cs_w[i + 1][j] + cs_w[i][j + 1] - cs_w[i][j] + white[i*K+j]

    ans = 0
    for i in range(K):
        for j in range(K):
            ans_b = cs_b[i][j] + cs_b[-1][-1] - cs_b[-1][j] - cs_b[i][-1] + cs_b[i][j]
            ans_w = cs_w[i][-1] - cs_w[i][j] + cs_w[-1][j] - cs_w[i][j]
            ans_w2 = cs_w[i][j] + cs_w[-1][-1] - cs_w[-1][j] - cs_w[i][-1] + cs_w[i][j]
            ans_b2 = cs_b[i][-1] - cs_b[i][j] + cs_b[-1][j] - cs_b[i][j]
            ans = max(ans, ans_b + ans_w, ans_b2 + ans_w2)

    print(ans)
    '''
    print(cs_b)
    print(cs_w)
    print(black)
    print(white)
    '''


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = [ int(v) for v in input().split() ]
hope = [ [ a for a in input().split() ] for i in range(n) ]

b_board = [ [ 0 for i in range(k)] for j in range(k) ]
w_board = [ [ 0 for i in range(k)] for j in range(k) ]
b_board_2 = [ [ 0 for i in range(k)] for j in range(k) ]
w_board_2 = [ [ 0 for i in range(k)] for j in range(k) ]
b_board_3 = [ [ 0 for i in range(k+1)] for j in range(k+1) ]
w_board_3 = [ [ 0 for i in range(k+1)] for j in range(k+1) ]

for h, w, c in hope:
    a1, a2 = divmod(int(w),k)
    b1, b2 = divmod(int(h),k)
    if (a1+b1) % 2 == 1:
        if c == "B":
            c = "W"
        else:
            c = "B"

    if c == "B":
        b_board[int(w)%k][int(h)%k] += 1
    else:
        w_board[int(w)%k][int(h)%k] += 1
    

for i in range(k):
    b, w = 0, 0
    for j in range(k):
        b += b_board[i][j]
        b_board_2[i][j] = b
        w += w_board[i][j]
        w_board_2[i][j] = w

for i in range(k):
    b, w = 0, 0
    for j in range(k):
        b += b_board_2[j][i]
        b_board_3[j+1][i+1] = b
        w += w_board_2[j][i]
        w_board_3[j+1][i+1] = w

total_b, total_w = b_board_3[k][k], w_board_3[k][k]
ans = 0

for i in range(1,k+1):
    for j in range(1,k+1):
        b1 = b_board_3[i][j] - b_board_3[0][j] - b_board_3[i][0]
        b2 = total_b - b_board_3[i][k] - b_board_3[k][j] + b_board_3[i][j]
        w1 = w_board_3[i][j] - w_board_3[0][j] - w_board_3[i][0]
        w2 = total_w - w_board_3[i][k] - w_board_3[k][j] + w_board_3[i][j]
        ans = max(b1+b2+(total_w-w1-w2),w1+w2+(total_b-b1-b2),ans)

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
xyc=[list(input().split()) for i in range(n)]
data=[[[] for i in range(k)] for j in range(k)]
B=[[0]*k for i in range(k)]
W=[[0]*k for i in range(k)]
for u in xyc:
    x=int(u[0])
    y=int(u[1])
    c=u[2]
    a,b=x%k,y%k
    if (x//k+y//k)%2==0:
        if c=="B":
            B[a][b]+=1
        else:
            W[a][b]+=1
    else:
        if c=="B":
            W[a][b]+=1
        else:
            B[a][b]+=1
lst=[[0]*k for i in range(k)]
li=[[0]*k for i in range(k)]
for i in range(k):
    lst[i][0]=B[i][0]
    li[i][0]=W[i][0]
    for j in range(1,k):
        lst[i][j]=lst[i][j-1]+B[i][j]
        li[i][j]=li[i][j-1]+W[i][j]
for i in range(1,k):
    for j in range(k):
        lst[i][j]+=lst[i-1][j]
        li[i][j]+=li[i-1][j]
det=[[0]*k for i in range(k)]
den=[[0]*k for i in range(k)]
for i in range(k):
    i=k-1-i
    det[i][k-1]=B[i][k-1]
    den[i][k-1]=W[i][k-1]
    for j in range(1,k):
        j=k-j-1
        det[i][j]=det[i][j+1]+B[i][j]
        den[i][j]=den[i][j+1]+W[i][j]
for i in range(1,k):
    i=k-i-1
    for j in range(k):
        j=k-j-1
        det[i][j]+=det[i+1][j]
        den[i][j]+=den[i+1][j]
bcount=lst[k-1][k-1]
wcount=li[k-1][k-1]
ans=max(bcount,wcount)
for i in range(k-1):
    for j in range(k-1):
        o=lst[i][j]+det[i+1][j+1]
        p=li[i][j]+den[i+1][j+1]
        ans=max(ans,o+wcount-p,bcount-o+p)
for i in range(k-1):
    o=lst[k-1][i]
    O=lst[i][k-1]
    p=li[k-1][i]
    P=li[i][k-1]
    ans=max(ans,bcount-o+p,wcount-p+o)
    ans=max(ans,bcount-O+P,wcount-P+O)
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    white = [[0] * K for _ in range(2*K)]
    for i in range(N):
        x, y, c = input().split()
        x, y = int(x) % (2*K), int(y) % (2*K)
        if y >= K:
            y -= K
            x = (x-K) % (2*K)
        if c == "W":
            white[x][y] += 1
        else:
            white[(x+K) % (2*K)][y] += 1
    ysum = [[0] * (2*K) for _ in range(2*K)]
    for i in range(2*K):
        ysum[i][0] = sum(white[i][:K])
        for j in range(1, K):
            ysum[i][j] = ysum[i][j-1] - white[i][j-1]
        for j in range(K+1, 2*K):
            ysum[i][j] = ysum[i][j-1] + white[i][(j+K-1) % (2*K)]
    csum = [[0] * (2*K) for _ in range(2*K)]
    ans = 0
    for i in range(2*K):
        csum[0][i] = sum([ysum[x][i] for x in range(K)]) + \
            sum([ysum[x][(i+K) % (2*K)] for x in range(K, 2*K)])
        for j in range(1, 2*K):
            csum[j][i] = csum[j-1][i] \
                + ysum[(j+K-1) % (2*K)][i] - ysum[(j+K-1) % (2*K)][(i+K) % (2*K)]\
                - ysum[j-1][i] + ysum[j-1][(i+K) % (2*K)]
    for i in range(2*K):
        for j in range(K):
            ans = max(ans, csum[i][j])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class ACC_2D:
    """
    二次元累積わ
    """

    def __init__(self, W, H):
        """
        W:幅
        H:高さ
        """

        self.W = W
        self.H = H
        self.mat = [[0]*(W+1) for _ in range(H+1)]

    def add(self, row, col, val):
        """
        matの値を変更する(初期化)
        row:たて(0<=row<H)
        col:横(0<=col<W)
        val:mat[row][col]を初期化する値
        """
        self.mat[row+1][col+1] += val

    def build(self):
        """
        累積和を計算する
        """
        for row in range(1, self.H+1):
            for col in range(1, self.W+1):
                self.mat[row][col] += self.mat[row][col-1] + \
                    self.mat[row-1][col] - self.mat[row-1][col-1]

    def get_val(self, g_row, g_col, s_row, s_col):
        """
        ２点で囲まれる長方形の、累積和を求める
        gx,gyは含まれない
        """
        return self.mat[g_row][g_col] - self.mat[s_row][g_col] - self.mat[g_row][s_col] + self.mat[s_row][s_col]


def solve():
    N, K = map(int, input().split())
    K2 = 2*K

    ACC = ACC_2D(K2, K2)

    # handle input
    # 全てを2K*2Kに圧縮する
    for _ in range(N):
        x, y, s = input().split()
        # 2K * 2Kに収める
        x = int(x)
        y = int(y)
        if s == "W":
            y += K
        x %= K2
        y %= K2

        ACC.add(x, y, 1)

    # 累積和をとる
    ACC.build()

    ans = 0
    # 黒としてチェックする
    # dは希望に沿っている数
    # ほんとは0~2Kで探さないといけないけど、N-dをついでにチェックすることで、半分でよくなる
    for row in range(K + 1):
        for col in range(K + 1):
            # 区間に入っている点の数
            d = ACC.get_val(row+K, col, row, 0)
            d += ACC.get_val(row, col+K, 0, col)
            d += ACC.get_val(K2, col+K, row+K, col)
            d += ACC.get_val(row+K, K2, row, col+K)
            ans = max(ans, d, N-d)
    print(ans)


solve()