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:
#二次元累積和
class CumulativeSum2D:
  def __init__(self,a):
    self.h=len(a)
    self.w=len(a[0])
    self.s=[(self.w+1)*[0]for _ in range(self.h+1)]
    for i in range(self.h):
      for j in range(self.w):
        self.s[i+1][j+1]=self.s[i+1][j]+self.s[i][j+1]-self.s[i][j]+a[i][j]
  def sum(self,i1,j1,i2,j2):
    return self.s[i2+1][j2+1]-self.s[i1][j2+1]-self.s[i2+1][j1]+self.s[i1][j1]

n,k=map(int,input().split())
b=[2*k*[0]for _ in range(2*k)]
for _ in range(n):
  x,y,c=input().split()
  x=int(x)
  y=int(y)
  if c=="B":y+=k
  x%=2*k
  y%=2*k
  b[x][y]=1
bs=CumulativeSum2D(b)
ans=bs.sum(0,0,k-1,k-1)+bs.sum(k,k,2*k-1,2*k-1)
ans=max(ans,bs.sum(k,0,2*k-1,k-1)+bs.sum(0,k,k-1,2*k-1))
for i in range(k,2*k):
  for j in range(k,2*k):
    t=bs.sum(i-k+1,j-k+1,i,j)+bs.sum(0,0,i-k,j-k)
    if i!=2*k-1:t+=bs.sum(i+1,0,2*k-1,j-k)
    if j!=2*k-1:t+=bs.sum(0,j+1,i-k,2*k-1)
    ans=max(ans,t)
print(ans)

Submission status: Wrong Answer

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_black=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
    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
    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
  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
  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
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)
    
print(max_answer)

Submission status: Wrong Answer

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 c=="W":
    amat_white[xx][yy]+=1
    num_white+=1
  else:
    amat_black[xx][yy]+=1
    num_black+=1
#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
for i in range(K):
  for j in range(K):
    answer_white=smat_white[i+K][j+K]-smat_white[i][j]
    answer_black=num_black-(smat_black[i+K][j+K]-smat_black[i][j])
    max_answer=max(max_answer,answer_white+answer_black)
    
print(max_answer)

Submission status: Wrong Answer

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

xyclist=[]
for i in range(N):
  x,y,c=input().split()  
  xx=int(x)%(2*K)
  yy=int(y)%(2*K)
  if xx>=K:
    xx-=K
    yy-=K
  if c=="W":
    cc=1
  else:
    cc=-1
    
  xyclist.append((xx,yy,cc))
xyclist.sort()
#print(xyclist)

max_answer=0
for i in range(K):
  for j in range(K):
    # white: y=0 to K-1, back: y=K to 2K-1
    answer=0
    miss=0
    for x,y,c in xyclist:
      xx=x-i
      yy=(y-j+K)%(2*K)-K
      if (2*xx+1)*(2*yy+1)*c>0:
        answer+=1
      else:
        miss+=1
        if miss>=N-max_answer:
          break
    
    if answer>max_answer:
      #max_answer=max(max_answer,answer)      
      max_answer=answer
      #print(i,j,answer)
    
print(max_answer)

Submission status: Wrong Answer

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

xyclist=[]
for i in range(N):
  x,y,c=input().split()  
  xx=int(x)%(2*K)
  yy=int(y)%(2*K)
  if xx>=K:
    xx-=K
    yy-=K
  if c=="W":
    cc=1
  else:
    cc=-1
    
  xyclist.append((xx,yy,cc))
xyclist.sort()
#print(xyclist)

max_answer=0
for i in range(K):
  for j in range(K):
    # white: y=0 to K-1, back: y=K to 2K-1
    answer=0
    miss=0
    for x,y,c in xyclist:
      xx=x-i
      yy=y-j
      if (2*xx+1)*(2*yy+1)*c>0:
        answer+=1
      else:
        miss+=1
        if miss>=N-max_answer:
          break
    
    if answer>max_answer:
      #max_answer=max(max_answer,answer)      
      max_answer=answer
      #print(i,j,answer)
    
print(max_answer)

Submission status: Wrong Answer

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

xyclist=[]
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:
    xx-=K
    yy-=K
  elif xx>=K and yy<K:
    xx-=K
    yy+=K
    
  if c=="W":
    cc=0
  else:
    cc=1
    
  xyclist.append((xx,yy,cc))
xyclist.sort()
#print(xyclist)

max_answer=0
for i in range(K):
  for j in range(K):
    # white: y=0 to K-1, back: y=K to 2K-1
    answer=0
    for x,y,c in xyclist:
      xx=(x-i)%(2*K)
      yy=(y-j)%(2*K)
      if xx>=K and yy>=K:
        xx-=K
        yy-=K
      elif xx>=K and yy<K:
        xx-=K
        yy+=K      
      if c==0 and yy<K:
        answer+=1
      elif c==1 and K<=yy:
        answer+=1
    
    if answer>max_answer:
      #max_answer=max(max_answer,answer)      
      max_answer=answer
      #print(i,j,answer)
    
print(max_answer)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
mod = 2*k
imos = [[0]*(mod+1) for i in range(mod+1)]
board = [[0]*mod for _ in range(mod)]
delta = [(0,0),(k,k),(k,-k),(-k,k),(-k,-k)]
m_cnt = 0
for i in range(n):
    x,y,c = input().split()
    x,y = map(int,[x,y])
    d = 1
    if c == 'W':
        x -= k
    x,y = x%mod,y%mod
    if (x//k) ^ (y//k):
        x = (x+k)%mod
        d *= -1
        m_cnt += 1
    if x < k or y < k:
        x += k
        y += k
    imos[x+1][y+1] += d
    imos[x-k+1][y-k+1] += d
    imos[x+1][y-k+1] -= d
    imos[x-k+1][y+1] -= d



for i in range(1,mod):
    for j in range(mod):
        imos[i][j] += imos[i-1][j]
ans = 0
for i in range(mod):
    for j in range(1,mod):
        imos[i][j] += imos[i][j-1]
        for di,dj in delta:
            if 0 <= i+di < mod and 0 <= j+dj < mod:
                board[i+di][j+dj] += imos[i][j]
                ans = max(ans,board[i+di][j+dj])
j = 0
for i in range(mod):
    ans = max(ans,board[i][j])
print(ans + m_cnt)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
mod = 2*k
imos = [[0]*(mod+1) for i in range(mod+1)]
board = [[0]*mod for _ in range(mod)]
delta = [(0,0),(k,k),(k,-k),(-k,k),(-k,-k)]
m_cnt = 0
for i in range(n):
    x,y,c = input().split()
    x,y = map(int,[x,y])
    d = 1
    if c == 'W':
        x -= k
    x,y = x%mod,y%mod
    if (x//k) ^ (y//k):
        x = (x+k)%mod
        d *= -1
        m_cnt += 1
    if x < k and y < k:
        x += k
        y += k
    imos[x+1][y+1] += d
    imos[x-k+1][y-k+1] += d
    imos[x+1][y-k+1] -= d
    imos[x-k+1][y+1] -= d



for i in range(1,mod):
    for j in range(mod):
        imos[i][j] += imos[i-1][j]
        if j == 0:
            for di,dj in delta:
                if 0 <= i+di < mod and 0 <= j+dj < mod:
                    board[i+di][j+dj] += imos[i][j]
ans = 0
for i in range(mod):
    for j in range(1,mod):
        imos[i][j] += imos[i][j-1]
        for di,dj in delta:
            if 0 <= i+di < mod and 0 <= j+dj < mod:
                board[i+di][j+dj] += imos[i][j]
                ans = max(ans,board[i+di][j+dj])
j = 0
for i in range(mod):
    ans = max(ans,board[i][j])
print(ans + m_cnt)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
mod = 2*k
imos = [[0]*(mod+1) for i in range(mod+1)]
board = [[0]*mod for _ in range(mod)]
delta = [(0,0),(k,k),(k,-k),(-k,k),(-k,-k)]
m_cnt = 0
for i in range(n):
    x,y,c = input().split()
    x,y = map(int,[x,y])
    d = 1
    if c == 'W':
        x -= k
    x,y = x%mod,y%mod
    if (x//k) ^ (y//k):
        x = (x+k)%mod
        d *= -1
        m_cnt += 1
    if x < k and y < k:
        x += k
        y += k
    imos[x+1][y+1] += d
    imos[x-k+1][y-k+1] += d
    imos[x+1][y-k+1] -= d
    imos[x-k+1][y+1] -= d



for i in range(1,mod):
    for j in range(mod):
        imos[i][j] += imos[i-1][j]
ans = 0
for i in range(2*k):
    for j in range(1,mod):
        imos[i][j] += imos[i][j-1]
        for di,dj in delta:
            if 0 <= i+di < mod and 0 <= j+dj < mod:
                board[i+di][j+dj] += imos[i][j]
                ans = max(ans,board[i+di][j+dj])
print(ans + m_cnt)

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
imos = [[0]*k for i in range(2*k)]
mod = 2*k
for i in range(n):
    x,y,c = input().split()
    x,y = map(int,[x,y])
    if c == 'W':
        x -= k
    x,y = x%mod,y%mod
    if y > k-1:
        x -= k
        y -= k
        x = x%mod
    if y == k-1:
        if x == 2*k - 1:
            imos[k][0] += 1
        elif x >= k-1:
            imos[x-k+1][0] += 1
            imos[x+1][0] -= 1
        else:
            imos[0][0] += 1
            imos[x+1][0] -= 1
            imos[x+1+k][0] += 1
    else:
        if x == 2*k - 1:
            imos[k][0] += 1
            imos[0][y+1] += 1
            imos[k][y+1] -= 2
        elif x >= k - 1:
            imos[x+1][0] -= 1
            imos[x+1-k][0] += 1
            imos[x+1][y+1] += 2
            imos[x+1-k][y+1] -= 2
            imos[0][y+1] += 1
        else:
            imos[x+1][0] -= 1
            imos[x+1][y+1] += 2
            imos[x+1+k][0] += 1
            imos[x+1+k][y+1] -= 2
            imos[0][0] += 1
            imos[0][y+1] -= 1
for i in range(1,2*k):
    for j in range(k):
        imos[i][j] += imos[i-1][j]
ans = 0
for i in range(2*k):
    for j in range(1,k):
        imos[i][j] += imos[i][j-1]
        ans = max(ans,imos[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:
def cumsum(T, K):
    R = [[0] * (K + 1) for _ in range(K + 1)]
    for i in range(K):
        t = 0
        for j in range(K):
            t += T[i][j]
            R[i][j] = t
    for i in range(K):
        t = 0
        for j in range(K):
            t += R[j][i]
            R[j][i] = t
    return R

def fm(B, W, K):
    m = 0
    for i in range(K):
        for j in range(K):
            t = B[i][j]
            if i == K - 1 or j == K - 1:
                t += W[K - 1][K - 1] - W[i][j]
            else:
                t += B[K - 1][K - 1] - B[K - 1][j] - B[i][K - 1] + B[i][j]
                t += W[K - 1][j] + W[i][K - 1] - W[i][j]
            m = max(m, t)
    return m

def main():
    N, K = map(int, input().split())
    K2 = 2 * K
    B = [[0] * K for _ in range(K)]
    W = [[0] * K for _ in range(K)]
    for _ in range(N):
        x1, y1, c = input().split()
        x, y = int(x1) % K2, int(y1) % K2
        if c == 'B':
            x = (x - K) % K2
        if x >= K and y >= K:
            x, y = x - K, y - K
        if x < K and y < K:
            B[x][y] += 1
        else:
            x, y = (x - K, y) if y < K else (x, y - K)
            W[x][y] += 1
    B = cumsum(B, K)
    W = cumsum(W, K)
    return max(fm(B, W, K), fm(W, B, K))

print(main())

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
ws = [[0] * K for _ in range(K)]
bs = [[0] * K for _ in range(K)]
for _ in range(N):
  x, y, c = input().split()
  x = int(x)
  y = int(y)
  t = x // K + y // K
  if t % 2:
    if c == "W": c = "B"
    if c == "B": c = "W"
  ws[y % K][x % K] += int(c == "W")
  bs[y % K][x % K] += int(c == "B")
#print(ws)
#print(bs)
csw = [[0] * (K + 1) for _ in range(K + 1)]
csb = [[0] * (K + 1) for _ in range(K + 1)]
for i in range(K):
  for j in range(K):
    csw[i + 1][j + 1] = csw[i + 1][j] + csw[i][j + 1] - csw[i][j] + ws[i][j]
    csb[i + 1][j + 1] = csb[i + 1][j] + csb[i][j + 1] - csb[i][j] + bs[i][j]
res = 0
for i in range(K + 1):
  for j in range(K + 1):
    u = csw[-1][-1] - csw[i][-1] - csw[-1][j] + csw[i][j] + csw[i][j]
    v = csb[i][-1] - csb[i][j] + csb[-1][j] - csb[i][j]
    res = max(res, u + v)
    u = csb[-1][-1] - csb[i][-1] - csb[-1][j] + csb[i][j] + csb[i][j]
    v = csw[i][-1] - csw[i][j] + csw[-1][j] - csw[i][j]
    res = max(res, u + v)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
ws = [[0] * K for _ in range(K)]
bs = [[0] * K for _ in range(K)]
for _ in range(N):
  x, y, c = input().split()
  x = int(x)
  y = int(y)
  t = x // K + y // K
  if t % 2:
    if c == "W": c = "B"
    if c == "B": c = "W"
  ws[y % K][x % K] += int(c == "W")
  bs[y % K][x % K] += int(c == "B")
#print(ws)
#print(bs)
csw = [[0] * (K + 1) for _ in range(K + 1)]
csb = [[0] * (K + 1) for _ in range(K + 1)]
for i in range(K):
  for j in range(K):
    csw[i + 1][j + 1] = csw[i + 1][j] + csw[i][j + 1] - csw[i][j] + ws[i][j]
    csb[i + 1][j + 1] = csb[i + 1][j] + csb[i][j + 1] - csb[i][j] + bs[i][j]
res = 0
for i in range(K + 1):
  for j in range(K + 1):
    u = csw[-1][-1] - csw[i][-1] - csw[-1][j] + csw[i][j] + csw[i][j]
    v = csb[i][-1] - csb[i][j] + csb[-1][j] - csb[i][j]
    res = max(res, u + v)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
ws = [[0] * K for _ in range(K)]
bs = [[0] * K for _ in range(K)]
for _ in range(N):
  x, y, c = input().split()
  x = int(x)
  y = int(y)
  t = x // K + y // K
  if t % 2:
    if c == "W": c = "B"
    if c == "B": c = "W"
  ws[y % K][x % K] += int(c == "W")
  bs[y % K][x % K] += int(c == "B")
#print(ws)
#print(bs)
csw = [[0] * (K + 1) for _ in range(K + 1)]
csb = [[0] * (K + 1) for _ in range(K + 1)]
for i in range(K):
  for j in range(K):
    csw[i + 1][j + 1] = csw[i + 1][j] + csw[i][j + 1] - csw[i][j] + ws[i][j]
    csb[i + 1][j + 1] = csb[i + 1][j] + csb[i][j + 1] - csb[i][j] + bs[i][j]
res = 0
for i in range(K):
  for j in range(K):
    u = csw[-1][-1] - csw[i][-1] - csw[-1][j] + csw[i][j] + csw[i][j]
    v = csb[i][-1] - csb[i][j] + csb[-1][j] - csb[i][j]
    res = max(res, u + v)
print(res)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
x=[0 for i in range(N)]
y=[0 for i in range(N)]
for i in range(N):
    a,b,c=map(str,input().split())
    a,b=int(a),int(b)
    a%=(2*K);b%=(2*K)
    if c=="B":
        a-=K
        a%=(2*K)
    x[i]=a
    y[i]=b
#x[i] in range(2*K)
#y[i] in range(2*K)
board=[[0 for j in range(2*K)] for i in range(2*K)]
Coard=[[0 for j in range(2*K+1)] for i in range(2*K)]
Doard=[[0 for j in range(2*K+1)] for i in range(2*K+1)]
for i in range(N):
    board[x[i]][y[i]]+=1
    board[(x[i]+K)%(2*K)][(y[i]+K)%(2*K)]+=1
for i in range(2*K):
    for j in range(2*K):
        Coard[i][j+1]=Coard[i][j]+board[i][j]
for i in range(2*K):
    for j in range(2*K+1):
        Doard[i+1][j]=Doard[i][j]+Coard[i][j]
ans=0
for i in range(K):
    for j in range(K):
        tmp=Doard[i][j]+Doard[i+K][j+K]-Doard[i][j+K]-Doard[i+K][j]
        ans=max(tmp,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc086/tasks/arc089_b
# 12:54-12:59 give up
# 13:02-13:56 done


def main():
    N, K = map(int, input().split())
    x, y, c = [None] * N, [None] * N, [None] * N
    for i in range(N):
        x[i], y[i], c[i] = map(
            lambda x: (-1 if x == "W" else 1) if x in ["B", "W"] else int(x),
            input().split()
        )

    origin_movex = x[0]
    origin_movey = y[0]
    for i in range(N):
        x[i] -= origin_movex
        y[i] -= origin_movey

    # x方向を0<=x<=(K-1)に収める
    for i in range(1, N):
        n_movex = x[i] // K
        x[i] = x[i] % K
        c[i] = -c[i] if n_movex % 2 > 0 else c[i]

    # y方向を-(K-1)<=y<=K-1に収める
    for i in range(1, N):
        n_movey = y[i] // K
        y[i] = y[i] % K
        c[i] = -c[i] if n_movey % 2 > 0 else c[i]

        if c[i] == -1:
            y[i] -= K
            c[i] = 1

    # now all black

    cnt = [0] * (2*K-1)
    for i in range(N):
        cnt[y[i]+(K-1)] += 1

    ans = sum(cnt[:K])
    now = ans
    for k in range(K, 2*K-1):
        now = now + cnt[k] - cnt[k-K-1]
        if now > ans:
            ans = now

    return ans


print(main())

Submission status: Wrong Answer

Solution code:
#縦k、横kのマスに移動させて考える
n, k = map(int, input().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = input().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

graph = [[0 for _ in range(k)] for __ in range(k)]

#累積和
#lx + lmx = n
lx = len(x)
for i in range(lx):
    graph[x[i]][y[i]] += 1

lmx = len(mx)
for i in range(lmx):
    graph[mx[i]][my[i]] -= 1

for i in range(k):
    for j in range(k-1):
        graph[i][j+1] += graph[i][j]

#最大値、最小値を取得
big = max([max(i) for i in graph]) + lmx
small = min([min(i) for i in graph]) - lx

if big + small >= 0:
    print(big)
else:
    print(-small)

Submission status: Wrong Answer

Solution code:
#縦k、横kのマスに移動させて考える
n, k = map(int, input().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = input().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

graph = [[0 for _ in range(k)] for __ in range(k)]

#累積和
#lx + lmx = n
lx = len(x)
for i in range(lx):
    for j in range(x[i], k):
        graph[j][y[i]] += 1
    for j in range(x[i] - 1):
        graph[j][0] += 1
        graph[j][y[i]] -= 1

lmx = len(mx)
for i in range(lmx):
    for j in range(mx[i], k):
        graph[j][my[i]] -= 1
    for j in range(mx[i] - 1):
        graph[j][0] -= 1
        graph[j][my[i]] += 1

for i in range(k):
    for j in range(k-1):
        graph[i][j+1] += graph[i][j]

#最大値、最小値を取得
big = max([max(i) for i in graph]) + lmx
small = min([min(i) for i in graph]) - lx

if big + small >= 0:
    print(big)
else:
    print(-small)

Submission status: Wrong Answer

Solution code:
#縦k、横kのマスに移動させて考える
n, k = map(int, input().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = input().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

graph = [[0 for _ in range(k)] for __ in range(k)]

#累積和
#lx + lmx = n
lx = len(x)
for i in range(lx):
    for j in range(x[i], k):
        graph[j][y[i]] += 1
    for j in range(x[i] - 1):
        graph[j][0] += 1
        graph[j][y[i]] -= 1

lmx = len(mx)
for i in range(lmx):
    for j in range(mx[i], k):
        graph[j][my[i]] -= 1
    for j in range(mx[i] - 1):
        graph[j][0] -= 1
        graph[j][my[i]] += 1

for i in range(k):
    for j in range(k-1):
        graph[i][j+1] += graph[i][j]

#最大値、最小値を取得
big = max([max(i) for i in graph]) + lmx
small = min([min(i) for i in graph]) - lx

if big + small >= 0:
    print(big)
else:
    print(-small)

Submission status: Wrong Answer

Solution code:
#縦k、横kのマスに移動させて考える
n, k = map(int, input().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = input().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

graph = [[0 for _ in range(k)] for __ in range(k)]

#累積和
#lx + lmx = n
lx = len(x)
for i in range(lx):
    for j in range(x[i], k):
        graph[j][y[i]] += 1

lmx = len(mx)
for i in range(lmx):
    for j in range(mx[i], k):
        graph[j][my[i]] -= 1

for i in range(k):
    for j in range(k-1):
        graph[i][j+1] += graph[i][j]

#最大値、最小値を取得
big = max([max(i) for i in graph]) + lmx
small = min([min(i) for i in graph]) - lx

if big + small >= 0:
    print(big)
else:
    print(-small)

Submission status: Wrong Answer

Solution code:
#縦k、横kのマスに移動させて考える
n, k = map(int, input().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = input().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

graph = [[0 for _ in range(k)] for __ in range(k)]

lx = len(x)
for i in range(lx):
    for j in range(x[i], k):
        for m in range(y[i], k):
            graph[j][m] += 1
lmx = n - lx
for i in range(lmx):
    for j in range(mx[i], k):
        for m in range(my[i], k):
            graph[j][m] -= 1

big = max([max(i) for i in graph]) + lmx
small = min([min(i) for i in graph]) - lx

if big + small >= 0:
    print(big)
else:
    print(-small)

Submission status: Wrong Answer

Solution code:
#縦k、横kのマスに移動させて考える
n, k = map(int, input().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = input().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

graph = [[0 for _ in range(k)] for __ in range(k)]

lx = len(x)
for i in range(lx):
    for j in range(x[i], k):
        for m in range(y[i], k):
            graph[j][m] += 1
lmx = len(mx)
for i in range(lmx):
    for j in range(mx[i], k):
        for m in range(my[i], k):
            graph[j][m] -= 1

big = max([max(i) for i in graph]) + lmx
small = min([min(i) for i in graph]) - lx

if big + small >= 0:
    print(big)
else:
    print(-small)

Submission status: Wrong Answer

Solution code:
#縦2*k、横2*kに移動させて考える
n, k = map(int, input().split())
x = []
y = []
for _ in range(n):
    xx, yy, c = input().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        xx -= k
        if yy >= k:
            yy -= k
        else:
            yy += k
    x.append(xx)
    y.append(yy)

graph = [[0 for _ in range(2*k)] for __ in range(k)]
for i in range(n):
    graph[x[i]][y[i]] += 1
for i in range(k):
    graph.append(graph[i][k:] + graph[i][:k])

ans = []
for i in range(k):
    for j in range(k):
        num = 0
        for l in range(k):
            for m in range(k):
                num += graph[i+l][j+m]
        ans.append(num)
print(max([max(ans), k - min(ans)]))

Submission status: Wrong Answer

Solution code:
#縦k、横kのマスに移動させて考える
n, k = map(int, input().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = input().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

lx = len(x)
graph = [[0 for _ in range(k)] for __ in range(k)]
for i in range(lx):
    for j in range(x[i], k):
        for m in range(y[i], k):
            graph[j][m] += 1

lmx = len(mx)
mgraph = [[0 for _ in range(k)] for __ in range(k)]
for i in range(lmx):
    for j in range(mx[i], k):
        for m in range(my[i], k):
            mgraph[j][m] += 1

dic = {(i, j):graph[i][j] - mgraph[i][j] for i in range(k) for j in range(k)}
big = max(dic.values()) + lmx
small = min(dic.values()) -lx

if big + small >= 0:
    print(big)
else:
    print(-small)

Submission status: Wrong Answer

Solution code:
import sys


N, K = map(int, input().split())
cnt_B = 0
black = [[0] * (2 * K) for _ in range(2 * K)]
for s in sys.stdin.readlines():
    x, y, c = s.split()
    x = int(x); y = int(y)
    y = y if c == 'B' else y + K
    black[x % (2 * K)][y % (2 * K)] += 1
    cnt_B += 1

S_black = [[0] * (2 * K + 1) for _ in range(2 * K)]
for i in range(2 * K):
    for j in range(2 * K):
        S_black[i][j + 1] = S_black[i][j] + black[i][j]

ans = 0
for j in range(K):
    var_B = 0
    for i in range(K):
        var_B += S_black[i][j + K] - S_black[i][j]
        var_B += S_black[i + K][2 * K] - (S_black[i + K][j + K] - S_black[i + K][j])

    ans = max(ans, var_B)
    for i in range(K):
        var_B += (S_black[i + K][j + K] - S_black[i + K][j]) - (S_black[i][j + K] - S_black[i][j])

        var_B -= S_black[i + K][2 * K] - (S_black[i + K][j + K] - S_black[i + K][j])
        var_B += S_black[i][2 * K] - (S_black[i][j + K] - S_black[i][j])

        ans = max(ans, var_B)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys


N, K = map(int, input().split())
cnt_B = 0
cnt_W = 0
black = [[0] * (2 * K) for _ in range(2 * K)]
white = [[0] * (2 * K) for _ in range(2 * K)]
for s in sys.stdin.readlines():
    x, y, c = s.split()
    x = int(x); y = int(y)
    if c == 'B':
        black[x % (2 * K)][y % (2 * K)] += 1
        cnt_B += 1
    else:
        white[x % (2 * K)][y % (2 * K)] += 1
        cnt_W += 1

S_black = [[0] * (2 * K + 1) for _ in range(2 * K)]
S_white = [[0] * (2 * K + 1) for _ in range(2 * K)]
for i in range(2 * K):
    for j in range(2 * K):
        S_black[i][j + 1] = S_black[i][j] + black[i][j]
        S_white[i][j + 1] = S_white[i][j] + white[i][j]

ans = 0
for j in range(K):
    var_B, var_W = 0, 0
    for i in range(K):
        var_B += S_black[i][j + K] - S_black[i][j]
        var_W += S_white[i][j + K] - S_white[i][j]
    ans = max(ans, max(var_B + (cnt_W - var_W), var_W + (cnt_B - var_B)))
    for i in range(K):
        var_B += (S_black[i + K][j + K] - S_black[i + K][j]) - (S_black[i][j + K] - S_black[i][j])
        var_W += (S_white[i + K][j + K] - S_white[i + K][j]) - (S_white[i][j + K] - S_white[i][j])
        ans = max(ans, max(var_B + (cnt_W - var_W), var_W + (cnt_B - var_B)))

print(ans)

Submission status: Wrong Answer

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

black = [[0] * (2 * k + 1) for _ in range(2 * k + 1)]
for x, y, c in xyc:
    xi, yi = int(x), int(y)
    if c == "W":
        xi += k
    xi, yi = xi % (2 * k) + 1, yi % (2 * k) + 1
    black[xi][yi] += 1


for i in range(2 * k):
    for j in range(2 * k + 1):
        black[i+1][j] += black[i][j]

for j in range(2 * k):
    for i in range(2 * k + 1):
        black[i][j+1] += black[i][j]


def cnt_square(lx, ly, rx, ry):
    lx += 1
    ly += 1
    rx += 1
    ry += 1
    ret = black[rx][ry]
    ret -= black[lx-1][ry]
    ret -= black[rx][ly-1]
    ret += black[lx-1][ly-1]
    return ret


def cnt_black(x, y):
    ret = cnt_square(0, 0, x - 1, y - 1)
    ret += cnt_square(x, y, x + k - 1, y + k - 1)
    ret += cnt_square(x + k, y + k, 2 * k - 1, 2 * k - 1)
    ret += cnt_square(0, y + k, x - 1, 2 * k - 1)
    ret += cnt_square(x + k, 0, 2 * k - 1, y - 1)
    return ret


ans = 0
for i in range(k + 1):
    for j in range(k + 1):
        cnt = cnt_black(i, j)
        ans = max(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
xyc = [list(input().split()) for i in range(n)]
for i in range(n):
  x,y,c = xyc[i]
  x = int(x)
  y = int(y)
  xq = x//k
  yq = y//k
  if (xq+yq)%2:
    if c == "B":
      c = "W"
    else:
      c = "B"
  x %= k
  y %= k
  xyc[i] = x,y,c
gridw = [[0 for i in range(k+1)] for j in range(k+1)]
gridb = [[0 for i in range(k+1)] for j in range(k+1)]
for x,y,c in xyc:
  x += 1
  y += 1
  if c == "B":
    gridb[x][y] += 1
  else:
    gridw[x][y] += 1
for grid in gridb,gridw:
  for i in range(1,k+1):
    for j in range(k+1):
      grid[i][j] += grid[i-1][j]
for grid in gridb,gridw:
  for i in range(k+1):
    for j in range(1,k+1):
      grid[i][j] += grid[i][j-1]
nw = gridw[-1][-1]
nb = gridb[-1][-1]
ans = 0
def sm(grid,i,j):
  return grid[i][j]+grid[-1][-1]-grid[-1][j]-grid[i][-1]+grid[i][j]
for i in range(k):
  for j in range(k):
    ans = max(ans,sm(gridb,i,j)+nw-sm(gridw,i,j))
print(ans)