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:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
l = 2 * k
acc = [[0] * 3 * k for _ in range(l)]
for _ in range(n):
    x, y, c = LS()
    x = int(x); y = int(y)
    if c == 'W':
        x += k
    x %= 2 * k
    y %= 2 * k
    acc[y][x] += 1
    for i, j in ((1, 1), (1, -1), (-1, 1), (-1, -1), (2, 0), (-2, 0)):
        if 0 <= y + k * i < l and 0 <= x + k * j < l:
            acc[y + k * i][x + k * j] += 1



acc = [[0] * (l + 1)] + [list(accumulate([0] + acc[y])) for y in range(l)]
for y in range(l):
    for x in range(l + 1):
        acc[y + 1][x] += acc[y][x]


ans = 0
for y in range(k + 1):
    for x in range(k + 1):
        ans = max(ans, acc[y + k][x + k] - acc[y][x + k] - acc[y + k][x] + acc[y][x])


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
l = 2 * k
acc = [[0] * l for _ in range(l)]
for _ in range(n):
    x, y, c = LS()
    x = int(x); y = int(y)
    if c == 'W':
        x += k
    x %= 2 * k
    y %= 2 * k
    acc[y][x] += 1
    for i, j in ((1, 1), (1, -1), (-1, 1), (-1, -1)):
        if 0 <= y + k * i < l and 0 <= x + k * j < l:
            acc[y + k * i][x + k * j] += 1



acc = [[0] * (l + 1)] + [list(accumulate([0] + acc[y])) for y in range(l)]
for y in range(l - 1):
    for x in range(l):
        acc[y + 1][x] += acc[y][x]


ans = 0
for y in range(k + 1):
    for x in range(k + 1):
        ans = max(ans, acc[y + k][x + k] - acc[y][x + k] - acc[y + k][x] + acc[y][x])


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
l = 2 * k
acc = [[0] * l for _ in range(l)]
for _ in range(n):
    x, y, c = LS()
    x = int(x); y = int(y)
    if c == 'W':
        x += k
    x %= 2 * k
    y %= 2 * k
    acc[y][x] += 1
    for i, j in ((1, 1), (1, -1), (-1, 1), (-1, -1)):
        if 0 <= y + k * i < l and 0 <= x + k * j < l:
            acc[y + k * i][x + k * j] += 1



for y in range(l):
    for x in range(l - 1):
        acc[y][x + 1] += acc[y][x]


for y in range(l - 1):
    for x in range(l):
        acc[y + 1][x] += acc[y][x]


ans = 0
for y in range(k):
    for x in range(k):
        ans = max(ans, acc[y + k][x + k] - acc[y][x + k] - acc[y + k][x] + acc[y][x])


print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
N, K = [int(_) for _ in input().split()]
XYC = []
b = np.zeros((4 * K + 1, 4 * K + 1), dtype=np.uint32)
for _ in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == 'W':
        y += K
    x %= (2 * K)
    y %= (2 * K)
    b[x + 1, y + 1] += 1
    b[x + 1, y + 2 * K + 1] += 1
    b[x + K + 1, y + K + 1] += 1
    b[x + 2 * K + 1, y + 2 * K + 1] += 1
acc = b.cumsum(axis=0).cumsum(axis=1)
ans = acc[K:, K:] - acc[:-K, K:] - acc[K:, :-K] + acc[:-K, :-K]
print(ans.max())

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
N, K = [int(_) for _ in input().split()]
XYC = []
b = np.zeros((4 * K + 1, 4 * K + 1), dtype=int)
for _ in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == 'W':
        y += K
    x %= (2 * K)
    y %= (2 * K)
    b[x + 1, y + 1] += 1
    b[x + 1, y + 2 * K + 1] += 1
    b[x + K + 1, y + K + 1] += 1
    b[x + 2 * K + 1, y + 2 * K + 1] += 1
acc = b.cumsum(axis=0).cumsum(axis=1)
ans = acc[K:, K:] - acc[:-K, K:] - acc[K:, :-K] + acc[:-K, :-K]
print(ans.max())

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
N, K = [int(_) for _ in input().split()]
XYC = []
b = np.zeros((4 * K, 4 * K), dtype=int)
for _ in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == 'W':
        y += K
    dy = 2 * K * (y // (2 * K))
    y -= dy
    x -= dy
    x %= 2 * K
    b[x, y] += 1
    b[x + 2 * K, y] += 1
    b[x, y + 2 * K] += 1
    b[x + 2 * K, y + 2 * K] += 1
c = np.pad(b, [(1, 0), (1, 0)], 'constant')
acc = c.cumsum(axis=0).cumsum(axis=1)
ans = max(acc[i + K, j + K] - acc[i, j + K] - acc[i + K, j] + acc[i, j]
          for i, j in itertools.product(range(2 * K), range(2 * K)))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
N, K = [int(_) for _ in input().split()]
XYC = []
b = np.zeros((2 * K, 2 * K), dtype=int)
for _ in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == 'W':
        y += K
    dy = K * (y // K)
    y -= dy
    x -= dy
    x %= 2 * K
    b[x, y] += 1
    b[(x + K) % (2 * K), y + K] += 1
c = np.pad(b, [(1, 0), (1, 0)], 'constant')
acc = c.cumsum(axis=0).cumsum(axis=1)
ans = max(acc[i + K, j + K] - acc[i, j + K] - acc[i + K, j] + acc[i, j]
          for i, j in itertools.product(range(K), range(K)))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
N, K = [int(_) for _ in input().split()]
XYC = []
b = np.zeros((2 * K, 2 * K), dtype=int)
for _ in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == 'W':
        y += K
    dy = K * (y // K)
    y -= dy
    x -= dy
    dx = 2 * K * (x // (2 * K))
    x -= dx
    b[x, y] += 1
    b[(x + K) % (2 * K), y + K] += 1
c = np.pad(b, [(1, 0), (1, 0)], 'constant')
acc = np.cumsum(np.cumsum(c, axis=0), axis=1)
ans = 0
for i, j in itertools.product(range(K), range(K)):
    ans = max(ans,
              acc[i + K, j + K] - acc[i, j + K] - acc[i + K, j] + acc[i, j])
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N,K = map(int,input().split())
x = np.array([])
y = np.array([])
c = np.array([])
max_request = 0

for i in range(N):
  t_x,t_y,t_c = input().split()
  x = np.append(x,[int(t_x)])
  y = np.append(y,[int(t_y)])
  c = np.append(c,[t_c])

for i in range(K):
  for j in range(K):
    w_odd = ()
    w_even = ()
    b_odd = ()
    b_even = ()

    for k in range(N):
      if c[k] == 'W':
        if int((x[k] + i-1) / K) + int((y[k] + j-1) / K) % 2 == 0:
          w_even += (1,)
        else:
          w_odd += (1,)
      if c[k] == 'B':
        if int((x[k] + i-1) / K) + int((y[k] + j-1) / K)%2 == 0:
          b_even += (1,)
        else:
          b_odd += (1,)

    if max_request < max([len(w_even)+len(b_odd),len(w_odd)+len(b_even)]):
      max_request = max([len(w_even)+len(b_odd),len(w_odd)+len(b_even)])

    if max_request == K:break
  if max_request == K:break

print(max_request)

Submission status: Wrong Answer

Solution code:
import numpy as np

N,K = map(int,input().split())
x = np.array([])
y = np.array([])
c = np.array([])
max_request = 0

for i in range(N):
  t_x,t_y,t_c = input().split()
  x = np.append(x,[int(t_x)])
  y = np.append(y,[int(t_y)])
  c = np.append(c,[t_c])

for i in range(K):
  for j in range(K):
    w_odd = ()
    w_even = ()
    b_odd = ()
    b_even = ()

    for k in range(N):
      if c[k] == 'W':
        if int((x[k] + i) / K) + int((y[k] + j) / K) % 2 == 0:
          w_even += (1,)
        else:
          w_odd += (1,)
      if c[k] == 'B':
        if int((x[k] + i) / K) + int((y[k] + j) / K)%2 == 0:
          b_even += (1,)
        else:
          b_odd += (1,)

    if max_request < max([len(w_even)+len(b_odd),len(w_odd)+len(b_even)]):
      max_request = max([len(w_even)+len(b_odd),len(w_odd)+len(b_even)])

    if max_request == K:break
  if max_request == K:break

print(max_request)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
w=[[0]*(k+1) for _ in range(k+1)]
b=[[0]*(k+1) for _ in range(k+1)]
for i in range(n):
    if ((int(l[i][0])//k+int(l[i][1])//k)%2==0)^(l[i][2]=='W'):
        b[int(l[i][0])%k][int(l[i][1])%k]+=1
    else:
        w[int(l[i][0])%k][int(l[i][1])%k]+=1

for i in range(1,k):
    b[0][i]+=b[0][i-1]
    b[i][0]+=b[i-1][0]
    w[0][i]+=w[0][i-1]
    w[i][0]+=w[i-1][0]
for i in range(1,k):
    for j in range(1,k):
        b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]
        w[i][j]+=w[i-1][j]+w[i][j-1]-w[i-1][j-1]

ans=0
for i in range(k):
    for j in range(k):
        ans=max(ans,b[k][k]-b[i][k]-b[k][j]+2*b[i][j]+w[i][k]+w[k][j]-2*w[i][j])
        ans=max(ans,w[k][k]-w[i][k]-w[k][j]+2*w[i][j]+b[i][k]+b[k][j]-2*b[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
w=[[0]*(k+1) for _ in range(k+1)]
b=[[0]*(k+1) for _ in range(k+1)]
for i in range(n):
    if ((int(l[i][0])//k+int(l[i][1])//k)%2==0) and l[i][2]=="B":
        b[int(l[i][0])%k][int(l[i][1])%k]+=1
    else:
        w[int(l[i][0])%k][int(l[i][1])%k]+=1

for i in range(1,k+1):
    b[0][i]+=b[0][i-1]
    b[i][0]+=b[i-1][0]
    w[0][i]+=w[0][i-1]
    w[i][0]+=w[i-1][0]
for i in range(1,k+1):
    for j in range(1,k+1):
        b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]
        w[i][j]+=w[i-1][j]+w[i][j-1]-w[i-1][j-1]

ans=0
for i in range(k+1):
    for j in range(k+1):
        ans=max(ans,b[k][k]-b[i][k]-b[k][j]+2*b[i][j]+w[i][k]+w[k][j]-2*w[i][j])
        ans=max(ans,w[k][k]-w[i][k]-w[k][j]+2*w[i][j]+b[i][k]+b[k][j]-2*b[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = [int(_) for _ in input().split()]
x = []
y = []
c = []
for i in range(0, n):
    t_x, t_y, t_c = input().split()
    x.append(int(t_x))
    y.append(int(t_y))
    c.append(t_c)

for i in range(0, n):
    if c[i] == 'W':
        c[i] = 'B'
        y[i] = y[i] + k

for i in range(0, n):
    x[i] = x[i] % (2*k)
    y[i] = y[i] % (2*k)


a = [[0 for _ in range(6*k)] for _ in range(6*k)]


for i in range(n):
    a[x[i]+1+(2*k-1)][y[i]+1+(2*k-1)] += 2
    a[x[i]+1+(2*k-1)][y[i]-k+1+(2*k-1)] -= 2
    a[x[i]+1+(2*k-1)][y[i]+1+k+(2*k-1)] -= 2
    a[x[i]+1+(2*k-1)][y[i]+1+2*k+(2*k-1)] += 1
    a[x[i]+1+(2*k-1)][y[i]+1-2*k+(2*k-1)] += 1


    a[x[i]-k+1+(2*k-1)][y[i]-k+1+(2*k-1)] += 2
    a[x[i]-k+1+(2*k-1)][y[i]+1+(2*k-1)] -= 2
    a[x[i]-k+1+(2*k-1)][y[i]+1+k+(2*k-1)] += 2
    a[x[i]-k+1+(2*k-1)][y[i]+1+2*k+(2*k-1)] -= 1
    a[x[i]-k+1+(2*k-1)][y[i]+1-2*k+(2*k-1)] -= 1


    a[x[i]+1+k+(2*k-1)][y[i]+1+(2*k-1)] -= 2
    a[x[i]+1+k+(2*k-1)][y[i]+1+k+(2*k-1)] += 2
    a[x[i]+1+k+(2*k-1)][y[i]+1+2*k+(2*k-1)] -= 1
    a[x[i]+1+k+(2*k-1)][y[i]+1-k+(2*k-1)] += 2
    a[x[i]+1+k+(2*k-1)][y[i]+1-2*k+(2*k-1)] -= 1


    a[x[i]+1+2*k+(2*k-1)][y[i]+1+(2*k-1)] += 1
    a[x[i]+1+2*k+(2*k-1)][y[i]+1+k+(2*k-1)] -= 1
    a[x[i]+1+2*k+(2*k-1)][y[i]+1+2*k+(2*k-1)] += 1
    a[x[i]+1+2*k+(2*k-1)][y[i]+1-k+(2*k-1)] -= 1


    a[x[i]+1-2*k+(2*k-1)][y[i]+1+(2*k-1)] += 1
    a[x[i]+1-2*k+(2*k-1)][y[i]+1+k+(2*k-1)] -= 1
    a[x[i]+1-2*k+(2*k-1)][y[i]+1-k+(2*k-1)] -= 1
    a[x[i]+1-2*k+(2*k-1)][y[i]+1-2*k+(2*k-1)] += 1




s = [[0 for _ in range(6*k)] for _ in range(6*k)]

s[0][0] = a[0][0]


for i in range(0, 6*k-1):
    for j in range(0, i+1):
        if j == 0:
            s[j][i+1] = s[j][i] + a[j][i+1]
        else:
            s[j][i+1] = s[j][i] + s[j-1][i+1] + a[j][i+1] - s[j-1][i]
    for l in range(0, i+1):
        if l == 0:
            s[i+1][l] = s[i][l] + a[i+1][l]
        else:
            s[i+1][l] = s[i][l] + s[i+1][l-1] + a[i+1][l] - s[i][l-1]
    s[i+1][i+1] = s[i][i+1] + s[i+1][i] + a[i+1][i+1] - s[i][i]


ans = 0
for i in range(0, 2*k):
    for j in range(0, 2*k):
        ans = max(ans, s[i+(k-1)][j+(k-1)])

print(ans)

Submission status: Wrong Answer

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

n,k = map(int, input().split())
grid = [[0]*k for i in range(k)]
black = 0
for i in range(n):
    a,b,c =input().split()
    a,b = int(a), int(b)
    f = a//k + b//k
    a %= k
    b %= k
    if (c == "W" and f%2==0) or (c == "B" and f%2==1):
        grid[a][b] += 1
    else:
        grid[a][b] -= 1
        black += 1

s = [[0]*(k+1) for i in range(k+1)]
for i in range(k):
    for j in range(k):
        s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + grid[i][j]

ans = 0
for i in range(k):
    for j in range(k):
        a = s[k][k] - s[i][k] - s[k][j] + 2*s[i][j] + black
        ans = max(ans, a)
print(ans)

Submission status: Wrong Answer

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

n,k = map(int, input().split())
grid = [[0]*k for i in range(k)]
for i in range(n):
    a,b,c =input().split()
    a,b = int(a)%k, int(b)%k
    grid[a][b] += 1 if c == "W" else -1

s = [[0]*(k+1) for i in range(k+1)]
for i in range(k):
    for j in range(k):
        s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + grid[i][j]
def get(x1,y1,x2,y2):
    return s[x2+1][y2+1] - s[x1][y2+1] - s[x2+1][y1] + s[x1][y1]

ans = 0
# (i,j)の位置全探索
for i in range(k):
    for j in range(k):
        a = s[i][j]
        b = s[k][j] - s[i][j]
        c = s[i][k] - s[i][j]
        d = s[k][k] - s[i][k] - s[k][j] + s[i][j]
        q = abs(a + d - b - c)
        ans = max(ans, q)
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
info = [list(input().split()) for i in range(n)]


cnt_b = [[0]*k for i in range(k)]
cnt_w = [[0]*k for i in range(k)]

for i in range(n):
    x, y, c = info[i]
    x, y = int(x), int(y)
    move_cnt = 0
    move_cnt += (x//k) + (y//k)
    if move_cnt % 2 == 0:
        if c == "B":
            cnt_b[x % k][y % k] += 1
        if c == "W":
            cnt_w[x % k][y % k] += 1
    if move_cnt % 2 == 1:
        if c == "B":
            cnt_w[x % k][y % k] += 1
        if c == "W":
            cnt_b[x % k][y % k] += 1

ruiseki_b = [[0]*(k+1) for i in range(k+1)]
ruiseki_w = [[0]*(k+1) for i in range(k+1)]
for i in range(k):
    for j in range(k):
        ruiseki_b[i+1][j+1] = ruiseki_b[i+1][j] + cnt_b[i][j]
        ruiseki_w[i+1][j+1] = ruiseki_w[i+1][j] + cnt_w[i][j]
for j in range(k):
    for i in range(k):
        ruiseki_b[i+1][j+1] += ruiseki_b[i][j+1]
        ruiseki_w[i+1][j+1] += ruiseki_w[i][j+1]
ans = 0
for i in range(k+1):
    for j in range(k+1):
        ans_b = ruiseki_b[k][k] - ruiseki_b[i][k] - ruiseki_b[k][j] + ruiseki_b[i][j]
        ans_w = ruiseki_w[i][k] + ruiseki_w[k][j] - ruiseki_w[i][j]
        ans = max(ans_w + ans_b, ans)
        ans_w = ruiseki_w[k][k] - ruiseki_w[i][k] - ruiseki_w[k][j] + ruiseki_w[i][j]
        ans_b = ruiseki_b[i][k] + ruiseki_b[k][j] - ruiseki_b[i][j]
        ans = max(ans_w + ans_b, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,k=map(int,input().split())
T=[[0]*(2*k+1) for _ in range(2*k+1)]
for i in range(n):
  x,y,c=map(str,(input().split()))
  x,y=int(x),int(y)
  if c=="B":
    T[x%(2*k)+1][y%(2*k)+1]+=1
  else:
    T[x%(2*k)+1][(y+k)%(2*k)+1]+=1
T=np.array(T)
T=np.cumsum(np.cumsum(T,axis=0),axis=1)

kk=2*k
ans=0
for i in range(k):
  for j in range(k):
    ans=max(ans,T[kk][kk]-T[j+k][kk]-T[kk][i+k]+T[j][kk]+T[kk][i]+2*T[j+k][i+k]-2*T[j+k][i]-2*T[j][i+k]+2*T[i][j])
print(ans)

Submission status: Wrong Answer

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

dp = [[0] * (3*K+1) for _ in range(3*K+1)]
for _ in range(N) :
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'W' :
        x += K
    
    m = min(x//K, y//K)
    x -= m * K
    y -= m * K
    x %= 2 * K
    y %= 2 * K
    
    dp[x][y] += 1
    if x < K and y < K :
        dp[x+K][y+K] += 1
        dp[x][y+2*K] += 1
        dp[x+2*K][y] += 1
    elif x < K and y >= K :
        dp[x+K][y-K] += 1
        dp[x+2*K][y] += 1
    elif x >= K and y < K :
        dp[x-K][y+K] += 1
        dp[x][y+2*K] += 1

for i in range(1, 3 * K) :
    dp[i][0] += dp[i-1][0]
for i in range(1, 3 * K) :
    dp[0][i] += dp[0][i-1]

for i in range(1, 3 * K) :
    for j in range(1, 3 * K) :
        dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
        
ret = 0
for i in range(K-1, 3 * K) :
    for j in range(K-1, 3 * K) :
        ret = max(ret, dp[i][j] - dp[i][j-K] - dp[i-K][j] + dp[i-K][j-K])
print(ret)

Submission status: Wrong Answer

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

dp = [[0] * (3*K+1) for _ in range(2*K+1)]
for _ in range(N) :
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'W' :
        x += K
    
    m = min(x//K, y//K)
    x -= m * K
    y -= m * K
    x %= 2 * K
    y %= 2 * K
    
    dp[x][y] += 1
    if x < K and y < K :
        dp[x+K][y+K] += 1
        dp[x][y+2*K] += 1
    elif x < K and y >= K :
        dp[x+K][y-K] += 1
    elif x >= K and y < K :
        dp[x-K][y+K] += 1
        dp[x][y+2*K] += 1

for i in range(1, 2 * K) :
    dp[i][0] += dp[i-1][0]
for i in range(1, 3 * K) :
    dp[0][i] += dp[0][i-1]

for i in range(1, 2 * K) :
    for j in range(1, 3 * K) :
        dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
        
ret = 0
for i in range(K-1, 2 * K) :
    for j in range(K-1, 3 * K) :
        ret = max(ret, dp[i][j] - dp[i][j-K] - dp[i-K][j] + dp[i-K][j-K])
print(ret)

Submission status: Wrong Answer

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

dp = [[0] * (2*K+1) for _ in range(2*K+1)]
for _ in range(N) :
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'W' :
        x += K
    
    m = min(x//K, y//K)
    x -= m * K
    y -= m * K
        
    x -= ((x+2 * K) // (2 * K) - 1) * 2 * K
    y -= ((y + 2 * K) // (2 * K) - 1) * 2 * K
    
    dp[x][y] += 1
    if x < K and y < K :
        dp[x+K][y+K] += 1
    elif x < K and y >= K :
        dp[x+K][y-K] += 1
    elif x >= K and y < K :
        dp[x-K][y+K] += 1


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

for i in range(1, 2 * K) :
    for j in range(1, 2 * K) :
        dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
        
ret = 0
for i in range(K-1, 2 * K) :
    for j in range(K-1, 2 * K) :
        ret = max(ret, dp[i][j] - dp[i][j-K] - dp[i-K][j] + dp[i-K][j-K])
print(ret)

Submission status: Wrong Answer

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

dp = [[0] * (3 * K + 1) for _ in range(3 * K + 1)]
for _ in range(N) :
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'W' :
        x += K
        y += K
        
    x -= ((x + 2 * K) // (2 * K) - 1) * 2 * K
    y -= ((y + 2 * K) // (2 * K) - 1) * 2 * K
    dp[y+K][x+K] += 1
    if y >= K :
        dp[y-K][x+K] += 1
    if x >= K :
        dp[y+K][x-K] += 1
    if y >= K and x >= K :
        dp[y-K][x-K] += 1


for i in range(1, 3 * K) :
    dp[0][i] += dp[0][i-1]
    dp[i][0] += dp[i-1][0]


for i in range(1, 3 * K) :
    for j in range(1, 3 * K) :
        dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
    
ret = 0
for i in range(K, 3 * K) :
    for j in range(K, 3 * K) :
        ret = max(ret, dp[i][j] - dp[i][j-K-1] - dp[i-K-1][j] + dp[i-K-1][j-K-1])
print(ret)

Submission status: Wrong Answer

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

dp = [[0] * (3 * K + 1) for _ in range(3 * K + 1)]
for _ in range(N) :
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'W' :
        x += K
        y += K
        
    x -= ((x + 2 * K) // (2 * K) - 1) * 2 * K
    y -= ((y + 2 * K) // (2 * K) - 1) * 2 * K
    dp[y+K][x+K] += 1
    if y >= K :
        dp[y-K][x+K] += 1
    if x >= K :
        dp[y+K][x-K] += 1
    if y >= K and x >= K :
        dp[y-K][x-K] += 1


for i in range(1, 3 * K) :
    dp[0][i] += dp[0][i-1]
    dp[i][0] += dp[i-1][0]


for i in range(1, 3 * K) :
    for j in range(1, 2 * K) :
        dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
    
ret = 0
for i in range(K, 3 * K) :
    for j in range(K, 2 * K) :
        ret = max(ret, dp[i][j] - dp[i][j-K-1] - dp[i-K-1][j] + dp[i-K-1][j-K-1])
print(ret)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(str, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    ans = ['Odd', 'Even']
    print(ans[(a*b)%2-1])
    return

#B
def B():
    a, b = map(str,input().split())
    a = a + b
    if math.sqrt(int(a)).is_integer():
        print("Yes")
    else:
        print("No")
    return

#C
def C():
    n = II()
    pre = (0, 0, 0)
    for _ in range(n):
        t,x,y = LI()
        dist = abs(pre[0] - x) + abs(pre[1] - y)
        if dist <= t - pre[2] and dist % 2 == (t - pre[2]) % 2:
            pre = (x, y, t)
            continue
        print("No")
        return
    print("Yes")
    return

#D
def D():
    n, k = LI()
    dp = [[0] * (2 * k + 1) for i in range(2 * k + 1)]
    for _ in range(n):
        x, y, c = LS()
        x, y = int(x), int(y)
        if c == "W":
            dp[(y + 1) % (2 * k)][(x + k + 1) % (2 * k)] += 1
        else:
            dp[(y + 1) % (2 * k)][(x + 1) % (2 * k)] += 1
    for y in range(2 * k + 1):
        for x in range(1, 2 * k + 1):
            dp[y][x] += dp[y][x - 1]
    for y in range(1, 2 * k + 1):
        for x in range(2 * k + 1):
            dp[y][x] += dp[y - 1][x]
    
    def count(l, r, d, u):
        return dp[d][l] - dp[d][r] - dp[u][l] + dp[u][r]
    
    ans = 0
    for i in range(k):
        for j in range(k):
            tmp = count(j, j + k, i, i + k) + count(0, j, 0, i) + count(j + k, 2 * k, 0, i) + count(0, j, i + k, 2 * k) + count(j + k, 2 * k, i + k, 2 * k)
            ans = max(ans, tmp, n - tmp)
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(str, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    ans = ['Odd', 'Even']
    print(ans[(a*b)%2-1])
    return

#B
def B():
    a, b = map(str,input().split())
    a = a + b
    if math.sqrt(int(a)).is_integer():
        print("Yes")
    else:
        print("No")
    return

#C
def C():
    n = II()
    pre = (0, 0, 0)
    for _ in range(n):
        t,x,y = LI()
        dist = abs(pre[0] - x) + abs(pre[1] - y)
        if dist <= t - pre[2] and dist % 2 == (t - pre[2]) % 2:
            pre = (x, y, t)
            continue
        print("No")
        return
    print("Yes")
    return

#D
def D():
    n, k = LI()
    dp = [[0] * (2 * k + 2) for i in range(2 * k + 2)]
    for _ in range(n):
        x, y, c = LS()
        x, y = int(x), int(y)
        if c == "W":
            dp[(y + 1) % (2 * k)][(x + k + 1) % (2 * k)] += 1
        else:
            dp[(y + 1) % (2 * k)][(x + 1) % (2 * k)] += 1
    for y in range(2 * k + 2):
        for x in range(1, 2 * k + 2):
            dp[y][x] += dp[y][x - 1]
    for y in range(1, 2 * k + 2):
        for x in range(2 * k + 2):
            dp[y][x] += dp[y - 1][x]
    
    def count(l, r, d, u):
        return dp[d][l] - dp[d][r] - dp[u][l] + dp[u][r]
    
    ans = 0
    for i in range(k):
        for j in range(k):
            tmp = count(j, j + k, i, i + k) + count(0, j, 0, i) + count(j + k, 2 * k, 0, i) + count(0, j, i + k, 2 * k) + count(j + k, 2 * k, i + k, 2 * k)
            ans = max(ans, tmp, n - tmp)
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
kibok = input().split()
kibo,k = int(kibok[0]),int(kibok[1])
#print(kibo,k)
loop=k*2
kibolist=[[0,0,"W"] for i in range(kibo)]
#print(len(kibox))
for i in range(kibo):
  kibon=input().split()
  kibox,kiboy,kiboc = int(kibon[0]),int(kibon[1]),kibon[2]
#  print(kibox,kiboy,kiboc)
  kibox=kibox%loop
  kiboy=kiboy%loop
#  print(kibox,kiboy,kiboc)
  kibolist[i]=(kibox,kiboy,kiboc)
#for i in range(kibo):
#  print(kibolist[i])
#white
maxkanaukibo=0
kanaukibo=0
m=0
for n in range(k):#0,1,k
  if maxkanaukibo==kibo:
    break
  for l in range(kibo):
    if (int((kibolist[l][0]+m)/k)+int((kibolist[l][1]+n)/k))%2==0:
      if kibolist[l][2]=='W':
        kanaukibo=kanaukibo+1
    if (int((kibolist[l][0]+m)/k)+int((kibolist[l][1]+n)/k))%2==1:
      if kibolist[l][2]=='B':
        kanaukibo=kanaukibo+1
  maxkanaukibo=max(kanaukibo,maxkanaukibo,kibo-kanaukibo)
  kanaukibo=0
n=0
for m in range(k):#0,1,k
  if maxkanaukibo==kibo:
    break
  for l in range(kibo):
    if (int((kibolist[l][0]+m)/k)+int((kibolist[l][1]+n)/k))%2==0:
      if kibolist[l][2]=='W':
        kanaukibo=kanaukibo+1
    if (int((kibolist[l][0]+m)/k)+int((kibolist[l][1]+n)/k))%2==1:
      if kibolist[l][2]=='B':
        kanaukibo=kanaukibo+1
  maxkanaukibo=max(kanaukibo,maxkanaukibo,kibo-kanaukibo)
  kanaukibo=0
print(maxkanaukibo)