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:
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])

xt = []
yt = []
ct = []
score = []
for n in range(N):
    flag = True
    xp = x[n] % (2 * K)
    yp = y[n] % (2 * K)
    for i in range(len(xt)):
        if xt[i] == xp and yt[i] == yp:
            flag = False
            idx = i
            break
    if flag:
        xt.append(xp)
        yt.append(yp)
        ct.append(c[n])
        score.append(1)
    else:
        score[idx] += 1
x = xt
y = yt
c = ct

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

print(result)

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    k2 = 2 * k
    w = [[0] * k2 for _ in range(k2)]
    b = [[0] * k2 for _ in range(k2)]
    for i in range(n):
        x, y, c = input().split()
        x = int(x) % k2
        y = int(y) % k2
        if c == 'W':
            w[x][y] += 1
        else:
            b[x][y] += 1
    best = 0
    for dx in range(k2):
        ww = w[:dx] + w[k+dx:]
        bb = b[dx:k+dx]
        for dy in range(k2):
            c = 0
            for www in ww:
                c += sum(www[:dy]) + sum(www[k+dy:])
            for bbb in bb:
                c += sum(bbb[dy:k+dy])
            best = max(best, c)
    print(best)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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])

xt = []
yt = []
score = []
for n in range(N):
    flag = True
    xp = x[n] % (2 * K)
    yp = y[n] % (2 * K)
    for i in range(len(xt)):
        if xt[i] == xp and yt[i] == yp:
            flag = False
            idx = i
            break
    if flag:
        xt.append(xp)
        yt.append(yp)
        score.append(1)
    else:
        score[idx] += 1
x = xt
y = yt

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

print(result)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split()) 
KK = 2*K
whites = [[0 for i in range(KK)] for j in range(K)]
total = [[0 for i in range(KK)] for j in range(K)]

for i in range(N):
	x,y,c = input().split()
	x,y = int(x), int(y)
	if c == 'B':
		if y >= K:
			y -= K
		else:
			y += K
	xx = x % K
	yy = y % KK
	whites[xx][yy] += 1

for x in range(K):
	for y in range(KK):
		tmp = whites[x][y]
		if x > 0:
			tmp += total[x-1][y]
		if y > 0:
			tmp += total[x][y-1]
			if x > 0:
				tmp -= total[x-1][y-1]
		total[x][y] = tmp
ans = 0
for y in range(K):
	tmp = total[K-1][y+K-1]
	if y > 0:
		tmp -= total[K-1][y-1]
	ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
x = []
y = []
c = []
ans = 0
for n in range(N):
    X,Y,C = map(str,input().split())
    x.append(int(X))
    y.append(int(Y))
    c.append(C)

for kx in range(K):
    for ky in range(K):
        num = 0
        for n in range(N):
            if ((x[n]-kx)//K)%2 == 0:
                xb = True
            else:
                xb = False
            if ((y[n]-ky)//K)%2 == 0:
                yb = True
            else:
                yb = False
            if xb == yb and c[n] == 'B':
                num += 1
            elif xb != yb and c[n] == 'W':
                num += 1
            if N-n+num < ans:
                break
        ans = max(ans,max(num,N-num))
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import heapq
import math
import sys

def hanten(c):
    if c == 'B':
        return 'W'
    else:
        return 'B'

tmp = input()
N, K = [int(a) for a in tmp.split()]
all_num = {'B': 0, 'W': 0}
requirements = [[0 for x in range(K)] for y in range(K)]
for n in range(N):
    tmp = input()
    x, y, c = [a for a in tmp.split()]
    x, y = int(x), int(y)
    x %= (K*2)
    y %= (K*2)
    x_pole = x // K
    y_pole = y // K
    assert x_pole <= 1 and y_pole <= 1
    if x_pole + y_pole == 1:
        c = hanten(c)
    requirements[x % K][y % K] += (1 if c == 'B' else -1)
    all_num[c] += 1

Colors = ['B', 'W']
max_ret = 0
for now_c in Colors:
    num = all_num[now_c]
    direction = 1 if now_c == 'W' else -1
    max_ret = max([max_ret, num])
    bx, ex = 0, K-1
    by, ey = 0, K-1
    while bx <= ex and by <= ey:
        # left ->
        ltor = sum([requirements[bx][y] for y in range(by, ey+1)]) * direction
        # right <-
        # rtol = sum([requirements[ex][y] for y in range(by, ey+1)]) * direction
        # top shita
        ttob = sum([requirements[x][by] for x in range(bx, ex+1)]) * direction
        # bottom ue
        # btot = sum([requirements[x][ey] for x in range(bx, ex+1)]) * direction
        results = [ltor, ttob]
        max_effective = max(results)
        if max_effective == ltor:
            bx += 1
        else:
            by += 1
        num += max_effective
        max_ret = max([max_ret, num])
print(max_ret)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import heapq
import math
import sys

def hanten(c):
    if c == 'B':
        return 'W'
    else:
        return 'B'

tmp = input()
N, K = [int(a) for a in tmp.split()]
requirements = [[{'B': 0, 'W': 0} for x in range(K)] for y in range(K)]
for n in range(N):
    tmp = input()
    x, y, c = [a for a in tmp.split()]
    x, y = int(x), int(y)
    x %= (K*2)
    y %= (K*2)
    x_pole = x // K
    y_pole = y // K
    assert x_pole <= 1 and y_pole <= 1
    if x_pole + y_pole == 1:
        c = hanten(c)
    requirements[x % K][y % K][c] += 1

Colors = ['B', 'W']
max_ret = 0
all_num = {'B': 0, 'W': 0}
for req1 in requirements:
    for req2 in req1:
        all_num['B'] += req2['B']
all_num['W'] += N - all_num['B']
for x in range(K):
    for y in range(K):
        requirements[x][y] = requirements[x][y]['B'] - requirements[x][y]['W']
for now_c in Colors:
    num = all_num[now_c]
    direction = 1 if now_c == 'W' else -1
    max_ret = max([max_ret, num])
    bx, ex = 0, K-1
    by, ey = 0, K-1
    while bx <= ex and by <= ey:
        # left ->
        ltor = sum([requirements[bx][y] for y in range(by, ey+1)]) * direction
        # right <-
        rtol = sum([requirements[ex][y] for y in range(by, ey+1)]) * direction
        # top shita
        ttob = sum([requirements[x][by] for x in range(bx, ex+1)]) * direction
        # bottom ue
        btot = sum([requirements[x][ey] for x in range(bx, ex+1)]) * direction
        results = [ltor, rtol, ttob, btot]
        max_effective = max(results)
        if max_effective == ltor:
            bx += 1
        elif max_effective == rtol:
            ex -= 1
        elif max_effective == ttob:
            by += 1
        else:
            ey -= 1
        num += max_effective
        max_ret = max([max_ret, num])
print(max_ret)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split()) 
KK = 2*K
whites = [[0 for i in range(KK)] for j in range(KK)]
total = [[0 for i in range(KK)] for j in range(KK)]

for i in range(N):
	x,y,c = input().split()
	x,y = int(x), int(y)
	if c == 'B':
		if x >= K:
			x -= K
		else:
			x += K
	xx = x % KK
	yy = y % KK
	whites[xx][yy] += 1
	whites[(xx+K)%KK][(yy+K)%KK] += 1

for x in range(KK):
	for y in range(KK):
		if x == 0:
			if y == 0:
				total[x][y] = whites[x][y]
			else:
				total[x][y] = total[x][y-1] + whites[x][y]
		else:
			if y == 0:
				total[x][y] = total[x-1][y] + whites[x][y]
			else:
				total[x][y] = total[x-1][y] + total[x][y-1] - total[x-1][y-1] + whites[x][y]

ans = 0
for x in range(K):
	for y in range(K):
		tmp = total[x+K-1][y+K-1]
		if x > 0:
			tmp -= total[x-1][y+K-1]
		if y > 0:
			tmp -= total[x+K-1][y-1]
			if x > 0:
				tmp += total[x-1][y-1]
		#if tmp > ans:
		#	print(x,y)
		ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    k2 = 2 * k
    ok = [0] * (k2 * k2)
    for i in range(n):
        x, y, c = input().split()
        if c == 'W':
            c = 0
        else:
            c = k
        x = int(x)
        y = int(y)
        for dx in range(k):
            dx = (x + dx + c) % k2 * k2
            for dy in range(k):
                dy = (y + dy + c) % k2
                ok[dx + dy] += 1
    print(ok)
    print(max(ok))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import heapq
import math
import sys

def hanten(c):
    if c == 'B':
        return 'W'
    else:
        return 'B'

tmp = input()
N, K = [int(a) for a in tmp.split()]
requirements = [[{'B': 0, 'W': 0} for x in range(K)] for y in range(K)]
for n in range(N):
    tmp = input()
    x, y, c = [a for a in tmp.split()]
    x, y = int(x), int(y)
    x %= (K*2)
    y %= (K*2)
    x_pole = x // K
    y_pole = y // K
    assert x_pole <= 1 and y_pole <= 1
    if x_pole + y_pole == 1:
        c = hanten(c)
    requirements[x % K][y % K][c] += 1

Colors = ['B', 'W']
max_ret = 0
all_num = {'B': 0, 'W': 0}
for req1 in requirements:
    for req2 in req1:
        all_num['B'] += req2['B']
all_num['W'] += N - all_num['B']
for now_c in Colors:
    num = all_num[now_c]
    max_ret = max([max_ret, num])
    bx, ex = 0, K-1
    by, ey = 0, K-1
    while bx <= ex and by <= ey:
        # left ->
        ltor = 0
        for y in range(by, ey+1):
            ltor -= requirements[bx][y][now_c]
            ltor += requirements[bx][y][hanten(now_c)]
        # right <-
        rtol = 0
        for y in range(by, ey+1):
            rtol -= requirements[ex][y][now_c]
            rtol += requirements[ex][y][hanten(now_c)]
        # top shita
        ttob = 0
        for x in range(bx, ex+1):
            ttob -= requirements[x][by][now_c]
            ttob += requirements[x][by][hanten(now_c)]
        # bottom ue
        btot = 0
        for x in range(bx, ex+1):
            btot -= requirements[x][ey][now_c]
            btot += requirements[x][ey][hanten(now_c)]
        results = [ltor, rtol, ttob, btot]
        max_effective = max(results)
        if max_effective == ltor:
            bx += 1
        elif max_effective == rtol:
            ex -= 1
        elif max_effective == ttob:
            by += 1
        else:
            ey -= 1
        num += max_effective
        max_ret = max([max_ret, num])
print(max_ret)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
x = []
y = []
c = []
for i in range(N):
    tmp_x, tmp_y, tmp_c = input().split()
    x.append(int(tmp_x))
    y.append(int(tmp_y))
    c.append(tmp_c)

def check(sx, sy, K, x, y):
    x = x % (2*K)
    y = y % (2*K)
    if x >= sx and y >= sy:
        return 'W'
    elif x < sx and y < sy:
        return 'W'
    else:
        return 'B'

ans = 0
for sx in range(K+1):
    for sy in range(K+1):
        r = 0
        for i in range(N):
            if check(sx, sy, K, x[i], y[i]) == c[i]:
                r = r + 1
        ans = max(ans, r)
print(ans)

Submission status: Wrong Answer

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(kx, 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)

            if max_n_desire == n:
                print(n)
                return

    print(max_n_desire)

solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n, k = map(int, input().split())
    k2 = k * 2
    t = [[0] * k2 for _ in range(k2)]
    for _ in range(n):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == "W": x += k
        x %= k2
        y %= k2
        t[x][y] += 1
        x = (x + k) % k2
        y = (y + k) % k2
        t[x][y] += 1
    # p2D(t)
    # print()
    for i in range(k2):
        ti = t[i]
        for j in range(1, k2):
            ti[j] += ti[j - 1]
    for j in range(k2):
        for i in range(1, k2):
            t[i][j] += t[i - 1][j]
    # p2D(t)
    ans = 0
    for i in range(k - 1, k2):
        for j in range(k - 1, k2):
            cur = t[i][j]
            if i - k >= 0: cur -= t[i - k][j]
            if j - k >= 0: cur -= t[i][j - k]
            if i >= k and j >= k: cur += t[i - k][j - k]
            ans=max(ans,cur,n-cur)
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
# 入力
N, K = map(int, input().split())
x, y, c = zip(*(((int(x), int(y), c)
              for x, y, c in (input().split() for _ in range(N)))))

K2 = 2 * K

# 各クエリを(0, 0)から(K -1, K - 1) の矩形にマッピングし、各マスの個数をカウント
cs = [
    [
        0
        for _ in range(K2)
    ]
    for _ in range(K2)
]
for i, j, k in zip(x, y, c):
    cs[(i + K * (k == 'W')) % K2][j % K2] += 1

# dp[i][j] はマス(i, j) から K*K のマスを黒で塗るときに叶えられる要望の数
dp = [
    [
        0
        for _ in range(K2)
    ]
    for _ in range(K2)
]
# 累積和を用いて解を求める
dp[0][0] = sum(
    cs[i][j]
    for i in range(K)
    for j in range(K)
)
for i in range(1, K + 1):
    dp[i][0] = dp[i - 1][0] + sum(
        cs[i + K - 1][j]
        for j in range(K)
    ) - sum(
        cs[i - 1][j]
        for j in range(K)
    )
    dp[0][i] = dp[0][i - 1] + sum(
        cs[j][i + K - 1]
        for j in range(K)
    ) - sum(
        cs[j][i - 1]
        for j in range(K)
    )
for i in range(K + 1, K2):
    dp[i][0] = dp[i - 1][0] + sum(
        cs[i - (K + 1)][j]
        for j in range(K)
    ) - sum(
        cs[i - 1][j]
        for j in range(K)
    )
    dp[0][i] = dp[0][i - 1] + sum(
        cs[j][i - (K + 1)]
        for j in range(K)
    ) - sum(
        cs[j][i - 1]
        for j in range(K)
    )
for i in range(1, K + 1):
    for j in range(1, K + 1):
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - \
            dp[i - 1][j - 1] + \
            cs[i + K - 1][j + K - 1] + \
            cs[i - 1][j - 1] - \
            cs[i - 1][j + K - 1] - \
            cs[i + K - 1][j - 1]
    for j in range(K + 1, K2):
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - \
            dp[i - 1][j - 1] + \
            cs[i + K - 1][j - (K + 1)] + \
            cs[i - 1][j - 1] - \
            cs[i - 1][j - (K + 1)] - \
            cs[i + K - 1][j - 1]
for i in range(K + 1, 2 * K):
    for j in range(1, K + 1):
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - \
            dp[i - 1][j - 1] + \
            cs[i - (K + 1)][j + K - 1] + \
            cs[i - 1][j - 1] - \
            cs[i - 1][j + K - 1] - \
            cs[i - (K + 1)][j - 1]
    for j in range(K + 1, K2):
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - \
            dp[i - 1][j - 1] + \
            cs[i - (K + 1)][j - (K + 1)] + \
            cs[i - 1][j - 1] - \
            cs[i - 1][j - (K + 1)] - \
            cs[i - (K + 1)][j - 1]
# 全通りの塗り方を試し、解を求める
ans = max(
    max(
        dp[i][j] + dp[i + K][j + K]
        for i in range(K)
        for j in range(K)
    ),
    max(
        dp[i][j] + dp[i - K][j + K]
        for i in range(K, K2)
        for j in range(K)
    ),
    max(
        dp[i][j] + dp[i + K][j - K]
        for i in range(K)
        for j in range(K, K2)
    ),
    max(
        dp[i][j] + dp[i - K][j - K]
        for i in range(K, K2)
        for j in range(K, K2)
    )
)

# 出力
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 入力
N, K = map(int, input().split())
x, y, c = zip(*(((int(x), int(y), c)
              for x, y, c in (input().split() for _ in range(N)))))

K2 = 2 * K

# 各クエリを(0, 0)から(K -1, K - 1) の矩形にマッピングし、各マスの個数をカウント
cs = [
    [
        0
        for _ in range(K2)
    ]
    for _ in range(K2)
]
for i, j, k in zip(x, y, c):
    cs[(i + K * (k == 'W')) % K2][j % K2] += 1

# dp[i][j] はマス(i, j) から K*K のマスを黒で塗るときに叶えられる要望の数
dp = [
    [
        0
        for _ in range(K2)
    ]
    for _ in range(K2)
]
# 累積和を用いて解を求める
dp[0][0] = sum(
    cs[i][j]
    for i in range(K)
    for j in range(K)
)
for i in range(1, K2):
    dp[i][0] = dp[i - 1][0] + sum(
        cs[(i + K - 1) % K2][j]
        for j in range(K)
    ) - sum(
        cs[i - 1][j]
        for j in range(K)
    )
    dp[0][i] = dp[0][i - 1] + sum(
        cs[j][(i + K - 1) % K2]
        for j in range(K)
    ) - sum(
        cs[j][i - 1]
        for j in range(K)
    )
for i in range(1, K2):
    for j in range(1, K2):
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - \
            dp[i - 1][j - 1] + \
            cs[(i + K - 1) % K2][(j + K - 1) % K2] + \
            cs[i - 1][j - 1] - \
            cs[i - 1][(j + K - 1) % K2] - \
            cs[(i + K - 1) % K2][j - 1]
# 全通りの塗り方を試し、解を求める
ans = max(
    dp[i][j] + dp[(i + K) % K2][(j + K) % K2]
    for i in range(K2)
    for j in range(K2)
)

# 出力
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 入力
N, K = map(int, input().split())
x, y, c = zip(*(((int(x), int(y), c)
              for x, y, c in (input().split() for _ in range(N)))))

# 各クエリを(0, 0)から(K -1, K - 1) の矩形にマッピングし、各マスの個数をカウント
cs = [
    [
        [
            0
            for _ in range(2 * K)
        ]
        for _ in range(2 * K)
    ]
    for _ in range(2)
]
for i, j, k in zip(x, y, c):
    cs[k == 'W'][i % (2 * K)][j % (2 * K)] += 1

# dp[k][i][j] はマス(i, j) から K*K のマスを色kで塗るときに叶えられる要望の数
dp = [
    [
        [
            0
            for _ in range(2 * K)
        ]
        for _ in range(2 * K)
    ]
    for _ in range(2)
]
# 累積和を用いて解を求める
for k in range(2):
    dp[k][0][0] = sum(
        cs[k][i][j]
        for i in range(K)
        for j in range(K)
    )
    for i in range(1, 2 * K):
        dp[k][i][0] = dp[k][i - 1][0] + sum(
            cs[k][(i + K - 1) % (2 * K)][j]
            for j in range(K)
        ) - sum(
            cs[k][i - 1][j]
            for j in range(K)
        )
        dp[k][0][i] = dp[k][0][i - 1] + sum(
            cs[k][j][(i + K - 1) % (2 * K)]
            for j in range(K)
        ) - sum(
            cs[k][j][i - 1]
            for j in range(K)
        )
for k in range(2):
    for i in range(1, 2 * K):
        for j in range(1, 2 * K):
            dp[k][i][j] = dp[k][i - 1][j] + dp[k][i][j - 1] - \
                dp[k][i - 1][j - 1] + \
                cs[k][(i + K - 1) % (2 * K)][(j + K - 1) % (2 * K)] + \
                cs[k][i - 1][j - 1] - \
                cs[k][i - 1][(j + K - 1) % (2 * K)] - \
                cs[k][(i + K - 1) % (2 * K)][j - 1]

# 全通りの塗り方を試し、解を求める
ans = max(
    dp[k][i][j] + dp[k][(i + K) % (2 * K)][(j + K) % (2 * K)] +
    dp[1 - k][(i + K) % (2 * K)][j] + dp[1 - k][i][(j + K) % (2 * K)]
    for k in range(2)
    for i in range(2 * K)
    for j in range(2 * K)
)

# 出力
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
T = [[0] * (2 * K + 5) for i in range(2 * K + 5)]
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'W':
        y += K
    T[x % (2 * K) + 1][y % (2 * K) + 1] += 1

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


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


num = 0
for i in range(K + 1):
    for j in range(K + 1):
        d = T[i][j]
        d += T[i + K][j + K] - T[i][j + K] - T[i + K][j] + T[i][j]
        d += T[2 * K][j] - T[i + K][j]
        d += T[i][2 * K] - T[i][j + K]
        d += T[2 * K][2 * K] - T[2 * K][j + K] - T[i + K][2 * K] + T[i + K][j + K]
        num = max(num, d)
        num = max(num, N - d)

print(num)

Submission status: Time Limit Exceeded

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

MeetDemand =[[0 for c in range(dK+1)] for r in range(dK)]
for i in range(N):
    x, y, c =input().split()
    x = int(x) % dK
    y = (int(y)+K if c=="W" else int(y)) % dK
    
    if 0 <= x < K and 0 <= y < K:
        MeetDemand[0][0] += 1
        MeetDemand[x+1][y+1] += 2
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][0] -= 1
        MeetDemand[0][y+K+1] += 1
        MeetDemand[x+1][y+K+1] -= 2
    elif 0 <= x < K:
        MeetDemand[0][y-K+1] += 1
        MeetDemand[x+1][y-K+1] -= 2
        MeetDemand[x+1][0] += 1
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][y+1] += 2
    elif 0 <= y < K:
        MeetDemand[x-K+1][0] += 1
        MeetDemand[x-K+1][y+1] -= 2
        MeetDemand[0][y+1] += 1
        MeetDemand[0][y+K+1] -= 1
        MeetDemand[x-K+1][y+K+1] += 2
    else:
        MeetDemand[0][0] += 1
        MeetDemand[0][y-K+1] -= 1
        MeetDemand[x-K+1][0] -= 1
        MeetDemand[x-K+1][y-K+1] += 2
        MeetDemand[0][y+1] += 1
        MeetDemand[x-K+1][y+1] -= 2

for x in range(K):
    for y in range(1, dK):
        MeetDemand[x][y] += MeetDemand[x][y-1]
for y in range(dK):
    for x in range(1, K):
        MeetDemand[x][y] += MeetDemand[x-1][y]

Ans = max(MeetDemand[0][:dK])
for i in range(1, K):
    Ans = max(Ans, max(MeetDemand[i][:dK]))
print(Ans)

Submission status: Time Limit Exceeded

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

MeetDemand =[[0 for c in range(dK+1)] for r in range(dK)]
for i in range(N):
    x, y, c =input().split()
    x = int(x) % dK
    y = int(y) 
    if c == "W":
        y += K
    y %= dK
    if 0 <= x < K and 0 <= y < K:
        MeetDemand[0][0] += 1
        MeetDemand[x+1][y+1] += 2
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][0] -= 1
        MeetDemand[0][y+K+1] += 1
        MeetDemand[x+1][y+K+1] -= 2
    elif 0 <= x < K:
        MeetDemand[0][y-K+1] += 1
        MeetDemand[x+1][y-K+1] -= 2
        MeetDemand[x+1][0] += 1
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][y+1] += 2
    elif 0 <= y < K:
        MeetDemand[x-K+1][0] += 1
        MeetDemand[x-K+1][y+1] -= 2
        MeetDemand[0][y+1] += 1
        MeetDemand[0][y+K+1] -= 1
        MeetDemand[x-K+1][y+K+1] += 2
    else:
        MeetDemand[0][0] += 1
        MeetDemand[0][y-K+1] -= 1
        MeetDemand[x-K+1][0] -= 1
        MeetDemand[x-K+1][y-K+1] += 2
        MeetDemand[0][y+1] += 1
        MeetDemand[x-K+1][y+1] -= 2

for x in range(K):
    for y in range(1, dK):
        MeetDemand[x][y] += MeetDemand[x][y-1]
Ans = max(MeetDemand[0][:dK])
for y in range(dK):
    for x in range(1, K):
        MeetDemand[x][y] += MeetDemand[x-1][y]
        Ans = max(Ans, MeetDemand[x][y])
print(Ans)

Submission status: Time Limit Exceeded

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

MeetDemand =[[0 for c in range(dK+1)] for r in range(dK)]
for i in range(N):
    x, y, c =input().split()
    x = int(x) % dK
    y = int(y) 
    if c == "W":
        y += K
    y %= dK
    if 0 <= x < K and 0 <= y < K:
        MeetDemand[0][0] += 1
        MeetDemand[x+1][y+1] += 2
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][0] -= 1
        MeetDemand[0][y+K+1] += 1
        MeetDemand[x+1][y+K+1] -= 2
    elif 0 <= x < K:
        MeetDemand[0][y-K+1] += 1
        MeetDemand[x+1][y-K+1] -= 2
        MeetDemand[x+1][0] += 1
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][y+1] += 2
    elif 0 <= y < K:
        MeetDemand[x-K+1][0] += 1
        MeetDemand[x-K+1][y+1] -= 2
        MeetDemand[0][y+1] += 1
        MeetDemand[0][y+K+1] -= 1
        MeetDemand[x-K+1][y+K+1] += 2
    else:
        MeetDemand[0][0] += 1
        MeetDemand[0][y-K+1] -= 1
        MeetDemand[x-K+1][0] -= 1
        MeetDemand[x-K+1][y-K+1] += 2
        MeetDemand[0][y+1] += 1
        MeetDemand[x-K+1][y+1] -= 2

for x in range(K):
    for y in range(1, dK+1):
        MeetDemand[x][y] += MeetDemand[x][y-1]
Ans = max(MeetDemand[0][:dK+1])
for y in range(dK+1):
    for x in range(1, K):
        MeetDemand[x][y] += MeetDemand[x-1][y]
        Ans = max(Ans, MeetDemand[x][y])
print(Ans)

Submission status: Time Limit Exceeded

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

MeetDemand =[[0 for c in range(dK+1)] for r in range(dK)]
for i in range(N):
    x, y, c =input().split()
    x = int(x)
    y = int(y)
    if c == "W":
        y += K
    x %= dK
    y %= dK
    if 0 <= x < K and 0 <= y < K:
        MeetDemand[0][0] += 1
        MeetDemand[x+1][y+1] += 2
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][0] -= 1
        MeetDemand[0][y+K+1] += 1
        MeetDemand[x+1][y+K+1] -= 2
    elif 0 <= x < K:
        MeetDemand[0][y-K+1] += 1
        MeetDemand[x+1][y-K+1] -= 2
        MeetDemand[x+1][0] += 1
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][y+1] += 2
    elif 0 <= y < K:
        MeetDemand[x-K+1][0] += 1
        MeetDemand[x-K+1][y+1] -= 2
        MeetDemand[0][y+1] += 1
        MeetDemand[0][y+K+1] -= 1
        MeetDemand[x-K+1][y+K+1] += 2
    else:
        MeetDemand[0][0] += 1
        MeetDemand[0][y-K+1] -= 1
        MeetDemand[x-K+1][0] -= 1
        MeetDemand[x-K+1][y-K+1] += 2
        MeetDemand[0][y+1] += 1
        MeetDemand[x-K+1][y+1] -= 2

for x in range(K+1):
    for y in range(1, dK+1):
        MeetDemand[x][y] += MeetDemand[x][y-1]
Ans = max(MeetDemand[0][:dK+1])
for y in range(dK+1):
    for x in range(1, K+1):
        MeetDemand[x][y] += MeetDemand[x-1][y]
        Ans = max(Ans, MeetDemand[x][y])
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
def count_bw(i,j,black_S_list,white_S_list,K):
    b=black_S_list[i+K][j+K]-black_S_list[i][j+K]-black_S_list[i+K][j]+black_S_list[i][j]
    w=white_S_list[i+K][j+K]-white_S_list[i][j+K]-white_S_list[i+K][j]+white_S_list[i][j]
    return b,w
  

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

black_list = [[0 for j in range(2*K)] for i in range(2*K)]
white_list = [[0 for j in range(2*K)] for i in range(2*K)]


for i in range(N):
    x,y,c=input().split()
    x=int(x)%(2*K)
    y=int(y)%(2*K)
    if c=="B":
        black_list[x][y]+=1
    else:
        white_list[x][y]+=1

black_S_list = [[0 for j in range(4*K+1)] for i in range(4*K+1)]
white_S_list = [[0 for j in range(4*K+1)] for i in range(4*K+1)]
for i in range(4*K):
    black_line_S = 0
    white_line_S = 0
    
    for j in range(4*K):
        black_line_S+=black_list[i%(2*K)][j%(2*K)]
        white_line_S+=white_list[i%(2*K)][j%(2*K)]
        black_S_list[i+1][j+1]=black_line_S+black_S_list[i][j+1]
        white_S_list[i+1][j+1]=white_line_S+white_S_list[i][j+1]

max_h=0
for i in range(2*K):
    for j in range(2*K):
        b1,w1=count_bw(i,j,black_S_list,white_S_list,K)
        b2,w2=count_bw(K+i,K+j,black_S_list,white_S_list,K)
        max_h=max(max_h,black_S_list[2*K][2*K]-b1-b2+w1+w2)
print(max_h)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
from operator import add
N,K=map(int,input().split())
L=2*K
Map=[[0]*L for i in range(L)]

for i in range(N):
  x,y,c=input().split()
  x,y=int(x),int(y)
  if c=="W":
    x-=K
  x,y=x%L,y%L
  if y>=K:
    x,y=(x-K)%L,y-K
    
  Map[x][y]+=1
  Map[x][y-K]+=-1
  if x!=K:
    Map[x-K][y-K]+=1
    Map[x-K][y]+=-1
  if x>K:
    Map[0][y]+=1
    Map[0][y-K]+=-1

Map=[accumulate(i) for i in Map]
Map=[accumulate(i) for i in zip(*Map)]
Map=list(map(list,zip(*Map)))
Map=[map(add, Map[i][:K], Map[i-K][K:]) for i in range(L)]

print(max(map(max,Map)))

Submission status: Time Limit Exceeded

Solution code:
def inpl(): return [int(i) for i in input().split()]

N, K = inpl()
import numpy as np
H = np.zeros((K,K), dtype = np.int32)
for _ in range(N):
    x, y, c = input().split() 
    x = int(x)
    y = int(y)
    t = True
    x %= 2*K
    y %= 2*K
    if x >= K:
        x -= K
        t = not t
    if y >= K:
        y -= K
        t = not t
    if c == 'W':
        t = not t
    if t:
        H[x][y] += 1
        continue
    H[x][y] -= 1

for i in range(K-1):
    H[i+1] += H[i]
H = H.T
for i in range(K-1):
    H[i+1] += H[i]
checkH =  np.zeros((K,K), dtype = np.int32)
for i in range(K):
    for j in range(K):
            checkH[i][j] = H[K-1][K-1] + 2*H[i][j] - H[i][K-1] - H[K-1][j] 
Hans = (N - checkH[K-1][K-1])//2 + checkH

print(max(np.amax(Hans), N-np.amin(Hans)))

Submission status: Time Limit Exceeded

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

def main():
    n, k = map(int, input().split())
    xn = []
    yn = []
    for i in range(n):
        x, y, c = input().split()
        x = int(x)
        y = int(y)
        assert c in ["W", "B"]
        if c == "W":
            y += k
        xn.append(x % (2 * k))
        yn.append(y % (2 * k))

    res = 0
    for i in range(2 * k):
        for j in range(2 * k):
            res = max(res, check(xn, yn, i, j, k))

    print(res)

def check(xn, yn, i, j, k):
    n = len(xn)
    res = 0
    for x, y in zip(xn, yn):
        xi = (x - i) % (2 * k)
        yj = (y - j) % (2 * k)
        if (xi >= k and yj >= k) or (xi < k and yj < k):
            res += 1
    return res

main()