Problem:


Score : 500 points

Problem Statement

AtCoDeer is thinking of painting an infinite two-dimensional grid in a checked pattern of side K.
Here, a checked pattern of side K is a pattern where each square is painted black or white so that each connected component of each color is a K × K square.
Below is an example of a checked pattern of side 3:

AtCoDeer has N desires.
The i-th desire is represented by x_i, y_i and c_i.
If c_i is B, it means that he wants to paint the square (x_i,y_i) black; if c_i is W, he wants to paint the square (x_i,y_i) white.
At most how many desires can he satisfy at the same time?

Constraints

1 ≤ N ≤ 10^5

1 ≤ K ≤ 1000

0 ≤ x_i ≤ 10^9

0 ≤ y_i ≤ 10^9

If i ≠ j, then (x_i,y_i) ≠ (x_j,y_j).

c_i is B or W.

N, K, x_i and y_i are integers.

Input

Input is given from Standard Input in the following format:

N K
x_1 y_1 c_1
x_2 y_2 c_2
:
x_N y_N c_N

Output

Print the maximum number of desires that can be satisfied at the same time.

Sample Input 1

4 3
0 1 W
1 2 W
5 3 B
5 4 B

Sample Output 1

4

He can satisfy all his desires by painting as shown in the example above.

Sample Input 2

2 1000
0 0 B
0 1 W

Sample Output 2

2

Sample Input 3

6 2
1 2 B
2 1 W
2 2 B
1 0 B
0 6 W
4 5 W

Sample Output 3

4



Sample input:
4 3
0 1 W
1 2 W
5 3 B
5 4 B


Sample output:
4

Submission status: Wrong Answer

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

N,K=rl()

W = [[0 for _ in range(2*K+3)] for _ in range(2*K+3)]
for i in range(N):
    x,y,c=input().split()
    x = int(x)%(2*K)
    y = (int(y) if c=='W' else int(y)+K)%(2*K)
    if (x<K)^(y<K):
        x %= K
        y %= K
        W[0][y+1] += 1
        W[x+1][y+1] -= 2
        W[0][K+1] -= 1
        W[x+1][K+1] += 1
        W[x+1][0] += 1
        W[K+1][0] -= 1
        W[K+1][y+1] += 1
    else:
        x %= K
        y %= K
        W[0][0] += 1
        W[x+1][0] -= 1
        W[0][y+1] -= 1
        W[x+1][y+1] += 2
        W[K+1][y+1] -= 1
        W[x+1][K+1] -= 1
        W[K+1][K+1] += 1

for x in range(0,K+2):
    for y in range(0,K+2):
        W[x][y] += W[x][y-1]
for y in range(0,K+2):
    for x in range(0,K+2):
        W[x][y] += W[x-1][y]

ans = 0
for x in range(K+1):
    for y in range(K+1):
        ans = max(ans,W[x][y])

print(ans)

Submission status: Wrong Answer

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

N,K=rl()

W = [[0 for _ in range(2*K+1)] for _ in range(2*K+1)]
for i in range(N):
    x,y,c=input().split()
    x = int(x)%(2*K)
    y = (int(y) if c=='W' else int(y)+K)%(2*K)
    if (x<K)^(y<K):
        x %= K
        y %= K
        W[0][y+1] += 1
        W[x+1][y+1] -= 2
        W[0][K+1] -= 1
        W[x+1][K+1] += 1
        W[x+1][0] += 1
        W[K+1][0] -= 1
        W[K+1][y+1] += 1
    else:
        x %= K
        y %= K
        W[0][0] += 1
        W[x+1][0] -= 1
        W[0][y+1] -= 1
        W[x+1][y+1] += 2
        W[K+1][y+1] -= 1
        W[x+1][K+1] -= 1
        W[K+1][K+1] += 1



for x in range(0,K+2):
    for y in range(0,K+2):
        W[x][y] += W[x][y-1]
for y in range(0,K+2):
    for x in range(0,K+2):
        W[x][y] += W[x-1][y]

ans = 0
for x in range(K+1):
    for y in range(K+1):
        ans = max(ans,W[x][y])

print(ans)

Submission status: Wrong Answer

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

N,K=rl()
X = [0]*N
Y = [0]*N
C = [0]*N
W = [[0 for _ in range(2*K+1)] for _ in range(2*K+1)]
for i in range(N):
    x,y,c=input().split()
    x = int(x)%(2*K)
    y = int(y)%(2*K)
    X[i] = x
    Y[i] = y
    if c == 'W':
        W[x][y] += 1
        C[i] = 0
    else:
        W[x][(y+K)%(2*K)] += 1
        C[i] = 1

for xy in range(1,2*K):
    W[xy][0] += W[xy-1][0]
    W[0][xy] += W[0][xy-1]
for x in range(1,2*K):
    for y in range(1,2*K):
        W[x][y] += W[x-1][y] + W[x][y-1] - W[x-1][y-1]

ans = 0
for x in range(K+1):
    for y in range(K+1):
        res = (W[x-1][y-1] +
        W[2*K-1][y-1] - W[x+K-1][y-1] + 
        W[x+K-1][y+K-1] - W[x-1][y+K-1] - W[x+K-1][y-1] + W[x-1][y-1] +
        W[x-1][2*K-1] - W[x-1][y+K-1] +
        W[2*K-1][2*K-1] - W[x+K-1][2*K-1] - W[2*K-1][y+K-1] + W[x+K-1][y+K-1])

        ans = max(ans,res)

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
favor = [tuple(input().split()) for _ in range(n)]
square = [[0 for _ in range(k)] for _ in range(k)]
initscore = 0
for xc, yc, c in favor:
    x = int(xc)
    y = int(yc)
    x %= 2*k
    y %= 2*k
    if (x in range(k) and y in range(k)) or (x in range(k, 2*k) and y in range(k, 2*k)):
        if c == 'B':
            square[x%k][y%k] += 1
        else:
            square[x%k][y%k] -= 1
            initscore += 1
    else:
        if c == 'B':
            square[x%k][y%k] -= 1
            initscore += 1
        else:
            square[x%k][y%k] += 1
cum = [[0 for _ in range(k+1)] for _ in range(k+1)]
for i in range(k):
    for j in range(k):
        cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + square[i][j]
maxscore = 0
for i in range(k):
    for j in range(k):
        score = 2*cum[i][j] - cum[i][k] - cum[k][j]
        maxscore = max(maxscore, abs(score))
print(maxscore + initscore + cum[k][k])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
favor = [tuple(input().split()) for _ in range(n)]
square = [[0 for _ in range(k)] for _ in range(k)]
initscore = 0
for x, y, c in favor:
    if c == 'W':
        initscore += 1
for xc, yc, c in favor:
    x = int(xc)
    y = int(yc)
    x %= 2*k
    y %= 2*k
    if (x in range(k) and y in range(k)) or (x in range(k, 2*k) and y in range(k, 2*k)):
        if c == 'B':
            square[x%k][y%k] += 1
        else:
            square[x%k][y%k] -= 1
    else:
        if c == 'B':
            square[x%k][y%k] -= 1
        else:
            square[x%k][y%k] += 1
cum = [[0 for _ in range(k+1)] for _ in range(k+1)]
for i in range(k):
    for j in range(k):
        cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + square[i][j]
maxscore = 0
for i in range(k):
    for j in range(k):
        score = 2*cum[i][j] - cum[i][k] - cum[k][j]
        maxscore = max(maxscore, n - initscore + abs(score))
print(maxscore)

Submission status: Wrong Answer

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

N,K=rl()
X = [0]*N
Y = [0]*N
C = [0]*N
W = [[0 for _ in range(2*K+1)] for _ in range(2*K+1)]
B = [[0 for _ in range(2*K+1)] for _ in range(2*K+1)]
for i in range(N):
    x,y,c=input().split()
    x = int(x)%(2*K)
    y = int(y)%(2*K)
    X[i] = x
    Y[i] = y
    if c == 'W':
        W[x][y] += 1
        C[i] = 0
    else:
        B[x][y] += 1
        C[i] = 1

for xy in range(1,2*K):
    W[xy][0] += W[xy-1][0]
    W[0][xy] += W[0][xy-1]
    B[xy][0] += B[xy-1][0]
    B[0][xy] += B[0][xy-1]
for x in range(1,2*K):
    for y in range(1,2*K):
        W[x][y] += W[x-1][y] + W[x][y-1] - W[x-1][y-1]
        B[x][y] += B[x-1][y] + B[x][y-1] - B[x-1][y-1]

ans = 0
for x in range(K+1):
    for y in range(K+1):
        res = (W[x-1][y-1] +
        B[x+K-1][y-1] - B[x-1][y-1] +
        W[2*K-1][y-1] - W[x+K-1][y-1] + 
        B[x-1][y+K-1] - B[x-1][y-1] +
        W[x+K-1][y+K-1] - W[x-1][y+K-1] - W[x+K-1][y-1] + W[x-1][y-1] +
        B[2*K-1][y+K-1] - B[x+K-1][y+K-1] - B[2*K-1][y-1] + B[x+K-1][y-1] +
        W[x-1][2*K-1] - W[x-1][y+K-1] +
        B[x+K-1][2*K-1] - B[x-1][2*K-1] - B[x+K-1][y+K-1] + B[x-1][y+K-1] + 
        W[2*K-1][2*K-1] - W[x+K-1][2*K-1] - W[2*K-1][y+K-1] + W[x+K-1][y+K-1])

        ans = max(ans,res)

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
favor = [tuple(input().split()) for _ in range(n)]
blacksquare = [[0 for _ in range(k)] for _ in range(k)]
whitesquare = [[0 for _ in range(k)] for _ in range(k)]
for xc, yc, c in favor:
    x = int(xc)
    y = int(yc)
    x %= 2*k
    y %= 2*k
    if (x in range(k) and y in range(k)) or (x in range(k, 2*k) and y in range(k, 2*k)):
        if c == 'B':
            blacksquare[x%k][y%k] += 1
        else:
            whitesquare[x%k][y%k] += 1
    else:
        if c == 'B':
            whitesquare[x%k][y%k] += 1
        else:
            blacksquare[x%k][y%k] += 1
blackcum = [[0 for _ in range(k+1)] for _ in range(k+1)]
whitecum = [[0 for _ in range(k+1)] for _ in range(k+1)]
for i in range(k):
    for j in range(k):
        whitecum[i+1][j+1] = whitecum[i+1][j] + whitecum[i][j+1] - whitecum[i][j] + whitesquare[i][j]
        blackcum[i+1][j+1] = blackcum[i+1][j] + blackcum[i][j+1] - blackcum[i][j] + blacksquare[i][j]
maxscore = 0
for i in range(k+1):
    for j in range(k+1):
        white = whitecum[i][k] + whitecum[k][j] - 2*whitecum[i][j]
        black = 2*blackcum[i][j] + blackcum[k][k] - blackcum[i][k] - blackcum[k][j]
        maxscore = max(maxscore, white + black)
print(maxscore)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
favor = [tuple(input().split()) for _ in range(n)]
blacksquare = [[0 for _ in range(k)] for _ in range(k)]
whitesquare = [[0 for _ in range(k)] for _ in range(k)]
for xc, yc, c in favor:
    x = int(xc)
    y = int(yc)
    x %= 2*k
    y %= 2*k
    if (x in range(k) and y in range(k)) or (x in range(k, 2*k) and y in range(k, 2*k)):
        if c == 'B':
            blacksquare[x%k][y%k] += 1
        else:
            whitesquare[x%k][y%k] += 1
    else:
        if c == 'B':
            whitesquare[x%k][y%k] += 1
        else:
            blacksquare[x%k][y%k] += 1
blackcum = [[0 for _ in range(k+1)] for _ in range(k+1)]
whitecum = [[0 for _ in range(k+1)] for _ in range(k+1)]
for i in range(k):
    for j in range(k):
        whitecum[i+1][j+1] = whitecum[i+1][j] + whitecum[i][j+1] - whitecum[i][j] + whitesquare[i][j]
        blackcum[i+1][j+1] = blackcum[i+1][j] + blackcum[i][j+1] - blackcum[i][j] + blacksquare[i][j]
maxscore = 0
for i in range(k):
    for j in range(k):
        white = whitecum[i][k] + whitecum[k][j] - 2*whitecum[i][j]
        black = 2*blackcum[i][j] + blackcum[k][k] - blackcum[i][k] - blackcum[k][j]
        maxscore = max(maxscore, white + black)
print(maxscore)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, K = map(int, input().split())
mod = 2*K
field = [[0]*(2*K+1) for _ in range(2*K+1)]

def gen_pattern(x):
    if x < K-1:
        return [[0, x+1], [x+K+1, 2*K]]
    else:
        return [[x-K+1, x+1]]

for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'W':
        y += K
    x %= mod
    y %= mod
    for tmp in [0, K]:
        for l, r in gen_pattern((x+tmp) % mod):
            for b, t in gen_pattern((y+tmp) % mod):
                print(l,r,b,t,x,y,tmp)
                field[l][b] += 1
                field[l][t] -= 1
                field[r][b] -= 1
                field[r][t] += 1
print(np.max(np.cumsum(np.cumsum(field, axis=0), axis=1)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

def main():
    na = list(map(int, input().split()))
    N = na[0]
    K = na[1]
    x = []
    y = []
    c = []
    for i in range(N):
        sa = input().split()
        x.append(int(sa[0]))
        y.append(int(sa[1]))
        c.append(True if sa[2] == 'W' else False)

    hopes = [[0 for j in range(K)] for i in range(K)]
    ysum = [[0 for j in range(K * 2)] for i in range(K)]

    score = 0
    for i in range(N):
        xmod = x[i] % K
        ymod = y[i] % K
        f = (int(x[i] / (K * 2)) + int(y[i] / (K * 2))) % 2 == 1
        c[i] ^= f
        if c[i]:
            score += 1
        h = -1 if c[i] else 1
        hopes[xmod][ymod] += h

    for i in range(K):
        s = 0
        for j in range(K):
            s += hopes[i][j]
            ysum[i][j] = s
        for j in range(K):
            s -= hopes[i][j]
            ysum[i][K + j] = s

    smax = 0
    for j in range(K * 2):
        s = 0
        for i in range(K):
            s += ysum[i][j]
            smax = max(smax, s)
        for i in range(K):
            s -= ysum[i][j]
            smax = max(smax, s)

    print(score + smax)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

def main():
    na = list(map(int, input().split()))
    N = na[0]
    K = na[1]
    x = []
    y = []
    c = []
    for i in range(N):
        sa = input().split()
        x.append(int(sa[0]))
        y.append(int(sa[1]))
        c.append(True if sa[2] == 'W' else False)

    hopes = [[0 for j in range(K)] for i in range(K)]
    ysum = [[0 for j in range(K * 2)] for i in range(K)]

    score = 0
    for i in range(N):
        xmod = x[i] % K
        ymod = y[i] % K
        f = (int(x[i] / K) + int(y[i] / K)) % 2 == 1
        c[i] ^= f
        if c[i]:
            score += 1
        h = -1 if c[i] else 1
        hopes[xmod][ymod] += h

    for i in range(K):
        s = 0
        for j in range(K):
            s += hopes[i][j]
            ysum[i][j] = s
        for j in range(K):
            s -= hopes[i][j]
            ysum[i][K + j] = s

    smax = 0
    for j in range(K * 2):
        s = 0
        for i in range(K):
            s += ysum[i][j]
            smax = max(smax, s)
        for i in range(K):
            s -= ysum[i][j]
            smax = max(smax, s)

    print(score + smax)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

def main():
    na = list(map(int, input().split()))
    N = na[0]
    K = na[1]
    x = []
    y = []
    c = []
    for i in range(N):
        sa = input().split()
        x.append(int(sa[0]))
        y.append(int(sa[1]))
        c.append(True if sa[2] == 'W' else False)

    hopes = [[0 for j in range(K)] for i in range(K)]
    ysum = [[0 for j in range(K * 2)] for i in range(K)]

    score = 0
    for i in range(N):
        xmod = x[i] % K
        ymod = y[i] % K
        f = (int(x[i] / K) + int(y[i] / K)) % 2 == 1
        c[i] ^= f
        if c[i]:
            score += 1
        hopes[xmod][ymod] = -1 if c[i] else 1

    for i in range(K):
        s = 0
        for j in range(K):
            s += hopes[i][j]
            ysum[i][j] = s
        for j in range(K):
            s -= hopes[i][j]
            ysum[i][K + j] = s

    smax = 0
    for j in range(K * 2):
        s = 0
        for i in range(K):
            s += ysum[i][j]
            smax = max(smax, s)
        for i in range(K):
            s -= ysum[i][j]
            smax = max(smax, s)

    print(score + smax)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

def main():
    na = list(map(int, input().split()))
    N = na[0]
    K = na[1]
    x = []
    y = []
    c = []
    for i in range(N):
        sa = input().split()
        x.append(int(sa[0]))
        y.append(int(sa[1]))
        c.append(True if sa[2] == 'W' else False)

    hopes = [[0 for j in range(K)] for i in range(K)]
    ysum = [[0 for j in range(K * 2)] for i in range(K)]

    score = 0
    for i in range(N):
        xmod = x[i] % K
        ymod = y[i] % K
        f = (int(x[i] / K) + int(y[i] / K) % 2 == 1)
        c[i] ^= f
        if c[i]:
            score += 1
        hopes[xmod][ymod] = -1 if c[i] else 1

    for i in range(K):
        s = 0
        for j in range(K):
            s += hopes[i][j]
            ysum[i][j] = s
        for j in range(K):
            s -= hopes[i][j]
            ysum[i][K + j] = s

    smax = 0
    for j in range(K * 2):
        s = 0
        for i in range(K):
            s += ysum[i][j]
            smax = max(smax, s)
        for i in range(K):
            s -= ysum[i][j]
            smax = max(smax, s)

    print(score + smax)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

def main():
    na = list(map(int, input().split()))
    N = na[0]
    K = na[1]
    x = []
    y = []
    c = []
    for i in range(N):
        sa = input().split()
        x.append(int(sa[0]))
        y.append(int(sa[1]))
        c.append(True if sa[2] == 'W' else False)

    hopes = [[0 for j in range(K)] for i in range(K)]
    ysum = [[0 for j in range(K * 2)] for i in range(K)]

    score = 0
    for i in range(N):
        xmod = x[i] % K
        ymod = y[i] % K
        f = (int(x[i] / K) + int(y[i] / K) % 2 == 1)
        c[i] ^= f
        if c[i]:
            score += 1
        hopes[xmod][ymod] = -1 if c[i] else 1

    for i in range(K):
        s = 0
        for j in range(K):
            s += hopes[i][j]
            ysum[i][j] = s
        for j in range(K):
            s -= hopes[i][j]
            ysum[i][K + j] = s

    smax = 0
    for j in range(K):
        s = 0
        for i in range(K):
            s += ysum[i][j]
            smax = max(smax, s)
        for i in range(K):
            s -= ysum[i][j]
            smax = max(smax, s)

    print(score + smax)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

def main():
    na = list(map(int, input().split()))
    N = na[0]
    K = na[1]
    x = []
    y = []
    c = []
    for i in range(N):
        sa = input().split()
        x.append(int(sa[0]))
        y.append(int(sa[1]))
        c.append(True if sa[2] == 'W' else False)

    hopes = [[0 for j in range(K * 3)] for i in range(K * 3)]
    xsum = [0 for j in range(K * 3)]
    ysum = [[0 for j in range(K * 3)] for i in range(K * 3)]

    for i in range(N):
        if c[i]:
            x[i] += K
        xmod = x[i] % (K * 2)
        ymod = y[i] % (K * 2)
        hopes[xmod][ymod] += 1
        if xmod < K and ymod < K:
            hopes[xmod][ymod + K * 2] += 1
            hopes[xmod + K][ymod + K] += 1
            hopes[xmod + K * 2][ymod] += 1
            hopes[xmod + K * 2][ymod + K * 2] += 1
        elif xmod < K:
            hopes[xmod + K][ymod - K] += 1
            hopes[xmod + K][ymod + K] += 1
            hopes[xmod + K * 2][ymod] += 1
        elif ymod < K:
            hopes[xmod - K][ymod + K] += 1
            hopes[xmod][ymod + K * 2] += 1
            hopes[xmod + K][ymod] += 1
        else:
            hopes[xmod - K][ymod - K] += 1
            hopes[xmod - K][ymod + K] += 1
            hopes[xmod + K][ymod - K] += 1
            hopes[xmod + K][ymod + K] += 1

    for j in range(K * 2):
        for i in range(K):
            xsum[j] += hopes[i][j]
    for i in range(K * 2):
        ysum[i][0] = s = sum(hopes[i][:K])
        for j in range(1, K * 2):
            s += (hopes[i][j + K - 1] - hopes[i][j - 1])
            ysum[i][j] = s

    h0 = []
    hmax = h = sum(xsum[:K])
    h0.append(h)
    for j in range(1, K * 2):
        h += (xsum[j + K - 1] - xsum[j - 1])
        hmax = max(hmax, h)
        h0.append(h)
    for j in range(K * 2):
        h = h0[j]
        for i in range(1, K * 2):
            h += (ysum[i + K - 1][j] - ysum[i - 1][j])
            hmax = max(hmax, h)

    print(hmax)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

def main():
    na = list(map(int, input().split()))
    N = na[0]
    K = na[1]
    x = []
    y = []
    c = []
    for i in range(N):
        sa = input().split()
        x.append(int(sa[0]))
        y.append(int(sa[1]))
        c.append(True if sa[2] == 'W' else False)

    hopes = [[0 for j in range(K * 2)] for i in range(K * 2)]
    xsum = [0 for j in range(K * 2)]
    ysum = [[0 for j in range(K * 2)] for i in range(K * 2)]

    for i in range(N):
        if c[i]:
            x[i] += K
        xmod = x[i] % (K * 2)
        ymod = y[i] % (K * 2)
        hopes[xmod][ymod] += 1
        if xmod < K and ymod < K:
            hopes[xmod + K][ymod + K] += 1
        elif xmod < K:
            hopes[xmod + K][ymod - K] += 1
        elif ymod < K:
            hopes[xmod - K][ymod + K] += 1
        else:
            hopes[xmod - K][ymod - K] += 1

    for j in range(K * 2):
        for i in range(K):
            xsum[j] += hopes[i][j]
    for i in range(K * 2):
        ysum[i][0] = s = sum(hopes[i][:K])
        for j in range(1, K):
            s += (hopes[i][j + K - 1] - hopes[i][j - 1])
            ysum[i][j] = s

    h0 = []
    hmax = h = sum(xsum[:K])
    h0.append(h)
    for j in range(1, K + 1):
        h += (xsum[j + K - 1] - xsum[j - 1])
        hmax = max(hmax, h)
        h0.append(h)
    for j in range(K + 1):
        h = h0[j]
        for i in range(1, K + 1):
            h += (ysum[i + K - 1][j] - ysum[i - 1][j])
            hmax = max(hmax, h)

    print(hmax)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

def main():
    na = list(map(int, input().split()))
    N = na[0]
    K = na[1]
    x = []
    y = []
    c = []
    for i in range(N):
        sa = input().split()
        x.append(int(sa[0]))
        y.append(int(sa[1]))
        c.append(True if sa[2] == 'W' else False)

    hopes = [[0 for j in range(K * 2)] for i in range(K * 2)]
    xsum = [0 for j in range(K * 2)]
    ysum = [[0 for j in range(K * 2)] for i in range(K * 2)]

    for i in range(N):
        if c[i]:
            x[i] += K
        xmod = x[i] % (K * 2)
        ymod = y[i] % (K * 2)
        hopes[xmod][ymod] += 1
        if xmod < K and ymod < K:
            hopes[xmod + K][ymod + K] += 1
        elif xmod < K:
            hopes[xmod + K][ymod - K] += 1
        elif ymod < K:
            hopes[xmod - K][ymod + K] += 1
        else:
            hopes[xmod - K][ymod - K] += 1

    for j in range(K * 2):
        for i in range(K):
            xsum[j] += hopes[i][j]
    for i in range(K * 2):
        ysum[i][0] = s = sum(hopes[i][:K])
        for j in range(1, K):
            s += (hopes[i][j + K - 1] - hopes[i][j - 1])
            ysum[i][j] = s

    h0 = []
    hmax = h = sum(xsum[:K])
    h0.append(h)
    for j in range(1, K):
        h += (xsum[j + K - 1] - xsum[j - 1])
        hmax = max(hmax, h)
        h0.append(h)
    for j in range(K):
        h = h0[j]
        for i in range(1, K):
            h += (ysum[i + K - 1][j] - ysum[i - 1][j])
            hmax = max(hmax, h)

    print(hmax)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
G = [[[0, 0] for j in range(2 * K + 1)] for i in range(2 * K + 1)]
W = 0
for i in range(N):
  x, y, c = input().split()
  G[int(x) % (2 * K) + 1][int(y) % (2 * K) + 1][0 if c == 'W' else 1] += 1
  W += 1 if c == 'W' else 0
for i in range(1, 2 * K + 1):
  for j in range(1, 2 * K + 1):
    G[i][j][0] += G[i][j - 1][0]
    G[i][j][1] += G[i][j - 1][1]
for i in range(1, 2 * K + 1):
  for j in range(1, 2 * K + 1):
    G[i][j][0] += G[i - 1][j][0]
    G[i][j][1] += G[i - 1][j][1]
cnt = 0
for i in range(1, K + 1):
  for j in range(1, K + 1):
    w = G[i - 1][j - 1][0] + G[i + K - 1][j + K - 1][0] - G[i - 1][j + K - 1][0] - G[i + K - 1][j - 1][0]
    b = G[i - 1][j - 1][1] + G[i + K - 1][j + K - 1][1] - G[i - 1][j + K - 1][1] - G[i + K - 1][j - 1][1]
    cnt = max([w + (N - W - b), (W - w) + b, cnt])
print(cnt)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
G = [[[0, 0] for j in range(2 * K + 1)] for i in range(2 * K + 1)]
W = 0
for i in range(N):
  x, y, c = input().split()
  G[int(x) % (2 * K)][int(y) % (2 * K)][0 if c == 'W' else 1] += 1
  W += 1 if c == 'W' else 0
for i in range(1, 2 * K + 1):
  for j in range(1, 2 * K + 1):
    G[i][j][0] = G[i][j - 1][0]
    G[i][j][1] = G[i][j - 1][1]
for i in range(1, 2 * K + 1):
  for j in range(1, 2 * K + 1):
    G[i][j][0] += G[i - 1][j][0]
    G[i][j][1] += G[i - 1][j][1]
cnt = 0
for i in range(1, K + 1):
  for j in range(1, K + 1):
    w = G[i - 1][j - 1][0] + G[i + K - 1][j + K - 1][0] - G[i - 1][j + K - 1][0] - G[i + K - 1][j - 1][0]
    b = G[i - 1][j - 1][1] + G[i + K - 1][j + K - 1][1] - G[i - 1][j + K - 1][1] - G[i + K - 1][j - 1][1]
    cnt = max([w + (N - W - b), W - w + b, cnt])
print(cnt)

Submission status: Wrong Answer

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

good=[ [0] * 2 * k for _ in range(2 * k) ]
bad=[ [0] * 2 * k for _ in range( 2*k ) ]

# 左上、右下が黒

for _ in range(n):
    x,y,c=input().split()
    x=int(x) % (2*k)
    y=int(y) % (2*k)
    if( ( x - k + 0.5) * ( y - k + 0.5 ) > 0):
        if( c == "B"):
            good[x][y]+=1
        else:
            bad[x][y]+=1
    else:
        if( c == "B"):
            bad[x][y]+=1
        else:
            good[x][y]+=1
    
good_sum=[ 0 ]*2*k
bad_sum=[0] * 2*k
for i in range(2*k):
    for j in range(2*k):
        good_sum[i] += good[i][j]
        bad_sum[i] += bad[i][j]

 
ans=[]
for i in range(k):
    if(i!=0):
        for j in range(2*k):
            good_sum[j] -= good[j][-i] - bad[j][-i] + good[j][k-i] - bad[j][k-i] 
            bad_sum[j] -= bad[j][-i] - good[j][-i]  + good[j][k-i] - bad[j][k-i]
    tmp=sum(good_sum)
    ans.append(tmp)
    ttmp=tmp
    for j in range(k):
        ttmp+=bad_sum[2*k - 1 -j] - good_sum[2*k-1-j] + bad_sum[k-1-j] - good_sum[k-1-j]
        ans.append(tmp)
    for j in range(k):
        tmp += bad_sum[j] - good_sum[j] + bad_sum[j-k] - good_sum[j-k]
        ans.append(tmp)
print(max(ans))

Submission status: Wrong Answer

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

good=[ [0] * 2 * k for _ in range(2 * k) ]
bad=[ [0] * 2 * k for _ in range( 2*k ) ]

# 左上、右下が黒

for _ in range(n):
    x,y,c=input().split()
    x=int(x) % (2*k)
    y=int(y) % (2*k)
    if( ( x - k + 0.5) * ( y - k + 0.5 ) > 0):
        if( c == "B"):
            good[x][y]+=1
        else:
            bad[x][y]+=1
    else:
        if( c == "B"):
            bad[x][y]+=1
        else:
            good[x][y]+=1
    
good_sum=[ 0 ]*2*k
bad_sum=[0] * 2*k
for i in range(2*k):
    for j in range(2*k):
        good_sum[i] += good[i][j]
        bad_sum[i] += bad[i][j]

 
ans=[]
for i in range(k):
    if(i!=0):
        for j in range(2*k):
            good_sum[j] -= good[j][-i] - bad[j][-i] + good[j][k-i] - bad[j][k-i] 
            bad_sum[j] -= bad[j][-i] - good[j][-i]  + good[j][k-i] - bad[j][k-i]
    tmp=sum(good_sum)
    ans.append(tmp)
    for j in range(k):
        tmp += bad_sum[j] - good_sum[j] + bad_sum[j-k] - good_sum[j-k]
        ans.append(tmp)
print(max(ans))

Submission status: Wrong Answer

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

good=[ [0] * 2 * k for _ in range(2 * k) ]
bad=[ [0] * 2 * k for _ in range( 2*k ) ]

# 左上、右下が黒

for _ in range(n):
    x,y,c=input().split()
    x=int(x) % (2*k)
    y=int(y) % (2*k)
    if( ( x - k + 0.5) * ( y - k + 0.5 ) >= 0):
        if( c == "B"):
            good[x][y]+=1
        else:
            bad[x][y]+=1
    else:
        if( c == "B"):
            bad[x][y]+=1
        else:
            good[x][y]+=1
    
good_sum=[ 0 ]*2*k
bad_sum=[0] * 2*k
for i in range(2*k):
    for j in range(2*k):
        good_sum[i] += good[i][j]
        bad_sum[i] += bad[i][j]

 
ans=[]
for i in range(2*k):
    if(i!=0):
        for j in range(2*k):
            good_sum[j] -= good[j][-i] - bad[j][-i] + good[j][-i+k] - bad[j][-i+k]
            bad_sum[j] -= bad[j][-i] - good[j][-i] + bad[j][-i+k] - good[j][-i+k]
    tmp=sum(good_sum)
    ans.append(tmp)
    for j in range(1,2*k):
        tmp += bad_sum[j] - good_sum[j] + bad_sum[j-k] - good_sum[j-k]
        ans.append(tmp)
print(max(ans))

Submission status: Wrong Answer

Solution code:
# time complexity: O(N + K^2)
# space complexity: O(K^2)

import sys
fin = sys.stdin.readline
from collections import defaultdict

def sum_range_2D(cuml_mat, coord_left_up, Kx, Ky):
    if Kx <= 0 or Ky <= 0:
        return 0
    x, y = coord_left_up
    if x - 1 >= 0 and y - 1 >= 0:
        left_up = cuml_mat[x - 1][y - 1]
    else:
        left_up = 0
    if x - 1 >= 0 and y + Ky - 1 >= 0:
        right_up = cuml_mat[x - 1][y + Ky - 1]
    else:
        right_up = 0
    if x + Kx - 1 >= 0 and y - 1 >= 0:
        left_down = cuml_mat[x + Kx - 1][y - 1]
    else:
        left_down = 0
    right_down = cuml_mat[min(len(cuml_mat) - 1, x + Kx - 1)][min(len(cuml_mat) - 1, y + Ky - 1)]
    return right_down - right_up - left_down + left_up


N, K = [int(elem) for elem in fin().split()]
black_desires = []
for _ in range(N):
    x, y, c = fin().split()
    x = int(x) % (2 * K)
    y = int(y) % (2 * K) if c == 'B' else (int(y) + K) % (2 * K)
    black_desires.append((x, y))

cuml_2D = [[0] * (2*K) for _ in range(2*K)]
for x, y in black_desires:
    cuml_2D[x][y] += 1
for i in range(2 * K):
    for j in range(1, 2 * K):
        cuml_2D[i][j] += cuml_2D[i][j - 1]
for j in range(2 * K):
    for i in range(1, 2 * K):
        cuml_2D[i][j] += cuml_2D[i - 1][j]

max_num = 0
for i in range(K + 1):
    for j in range(K):
        current_num = sum_range_2D(cuml_2D, (i, j), K, K) \
                    + sum_range_2D(cuml_2D, (0, 0), i, j) \
                    + sum_range_2D(cuml_2D, (0, j + K), i, K - j) \
                    + sum_range_2D(cuml_2D, (i + K, 0), K - i, j) \
                    + sum_range_2D(cuml_2D, (i + K, j + K), K - i, K - j)
        max_num = max(max_num, current_num)

for i in range(K + 1):
    for j in range(K, 2 * K):
        current_sum = sum_range_2D(cuml_2D, (i, j), K, 2 * K - j) \
                    + sum_range_2D(cuml_2D, (0, j - K), i, K) \
                    + sum_range_2D(cuml_2D, (i + K, j - K), K - i, K) \
                    + sum_range_2D(cuml_2D, (i, 0), K, j - K)
        max_num = max(max_num, current_num)
print(max_num)