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 = 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+1):
  for j in range(k+1):
    ans = max(ans,sm(gridb,i,j)+nw-sm(gridw,i,j))
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
mod = K * 2
XY = []
MAX = K * 4
acc = list2d(MAX, MAX, 0)
for i in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    x %= mod
    y %= mod
    if c == 'B':
        x += K
    for a1 in range(3):
        for a2 in range(3):
            for b in [0, K]:
                if c == 'B':
                    b = -b
                x1 = x + a1 * mod + b
                y1 = y + a2 * mod + b
                x2 = x1 + K
                y2 = y1 + K
                x1 = max(min(x1, MAX-1), 0)
                y1 = max(min(y1, MAX-1), 0)
                x2 = max(min(x2, MAX-1), 0)
                y2 = max(min(y2, MAX-1), 0)
                acc[x1][y1] += 1
                acc[x2][y2] += 1
                acc[x1][y2] -= 1
                acc[x2][y1] -= 1

for i in range(MAX):
    acc[i] = list(accumulate(acc[i]))
for j in range(MAX):
    for i in range(MAX-1):
        acc[i+1][j] += acc[i][j]
ans = 0
for i in range(K*2, K*4):
    ans = max(ans, max(acc[i][K*2:K*4]))
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
mod = K * 2
XY = []
MAX = K*6 + 7
acc = list2d(MAX, MAX, 0)
for i in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == 'B':
        x += K
    for a1 in range(3):
        for a2 in range(3):
            for b in [0, K]:
                if c == 'B':
                    b = -b
                x1 = x + a1 * K*2 + b
                y1 = y + a2 * K*2 + b
                x2 = x1 + K
                y2 = y1 + K
                x1 = max(min(x1, MAX-1), 0)
                y1 = max(min(y1, MAX-1), 0)
                x2 = max(min(x2, MAX-1), 0)
                y2 = max(min(y2, MAX-1), 0)
                acc[x1][y1] += 1
                acc[x2][y2] += 1
                acc[x1][y2] -= 1
                acc[x2][y1] -= 1

for i in range(MAX):
    acc[i] = list(accumulate(acc[i]))
for j in range(MAX):
    for i in range(MAX-1):
        acc[i+1][j] += acc[i][j]
mx = 0
for j in range(K*2, K*4):
    for i in range(K*2, K*4):
        mx = max(mx, acc[i][j])
print(mx)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
mod = K * 2
XY = []
MAX = K*6 + 7
acc = list2d(MAX, MAX, 0)
for i in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == 'B':
        x += K
    for a1 in range(3):
        for a2 in range(3):
            for b in [0, K]:
                if c == 'B':
                    b = -b
                x1 = x + a1 * K*2 + b
                y1 = y + a2 * K*2 + b
                x2 = x1 + K
                y2 = y1 + K
                x1 = max(min(x1, MAX-1), 0)
                y1 = max(min(y1, MAX-1), 0)
                x2 = max(min(x2, MAX-1), 0)
                y2 = max(min(y2, MAX-1), 0)
                acc[x1][y1] += 1
                acc[x2][y2] += 1
                acc[x1][y2] -= 1
                acc[x2][y1] -= 1

for i in range(MAX):
    acc[i] = list(accumulate(acc[i]))
for j in range(MAX):
    for i in range(MAX-1):
        acc[i+1][j] += acc[i][j]
mx = 0
for j in range(MAX):
    for i in range(MAX):
        mx = max(mx, acc[i][j])
print(mx)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def query_cumsum2d(s, x1, y1, x2, y2):
    # [x1, x2) × [y1, y2)
    if x2 < x1:
        x1, x2 = x2, x1
    if y2 < y1:
        y1, y2 = y2, y1
    return s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]

def main():
    N, K = LI()
    G = [[0 for _ in range(2*K)] for __ in range(2*K)]
    cumsum2d = [[0 for _ in range(2*K + 1)] for __ in range(2*K + 1)]
    xyc = []
    for _ in range(N):
        x, y, c =  LS()
        x = int(x)
        y = int(y)
        if c == 'W':
            x += K
        x = x % (2 * K)
        y = y % (2 * K)
        G[x][y] += 1
        xyc.append((x, y, c))
    for x in range(2*K):
        for y in range(2*K):
            cumsum2d[x+1][y+1] = (
                cumsum2d[x+1][y]
                + cumsum2d[x][y+1]
                - cumsum2d[x][y]
                + G[x][y]
            )
    ans = 0
    # import pdb
    # print('cum: ')
    # for row in cumsum2d:
    #     print(row)
    # print()
    # print('g: ')
    # for row in G:
    #     print(row)
    for x in range(K):
        for y in range(K):
            # pdb.set_trace()
            cnt = (
                  query_cumsum2d(cumsum2d, 0, 0, x, y)
                + query_cumsum2d(cumsum2d, x, y, x+K, y+K)
                + query_cumsum2d(cumsum2d, x+K, 0, 2 * K, y)
                + query_cumsum2d(cumsum2d, 0, y+K, x, 2 * K)
                + query_cumsum2d(cumsum2d, 2*K, 2*K, x+K, y+K)
            )

            ans = max(ans, cnt)
    print(ans)



main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def valid_board(off_x, off_y, off_c, x, y, c):
    dx = abs(x - off_x)
    dy = abs(y - off_y)
    r = dx // 3 + dy // 3
    if r % 2 == 0:
        return c == off_c
    return c != off_c

def main():
    N, K = LI()
    xyc = []
    for _ in range(N):
        _xyc = LS()
        xyc.append(_xyc)
    ans = 0
    for off_x in range(-3, 0):
        for off_y in range(-3, 0):
            for off_c in ['B', 'W']:
                cnt = 0
                for x, y, c in xyc:
                    if not valid_board(off_x, off_y, off_c, int(x), int(y), c):
                        continue
                    cnt += 1
                ans = max(ans, cnt)
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def valid_board(off_x, off_y, off_c, x, y, c):
    dx = x - off_x
    dy = y - off_y
    r = dx // 3 + dy // 3
    if r % 2 == 0:
        return c == off_c
    return c != off_c

def main():
    N, K = LI()
    xyc = []
    for _ in range(N):
        _xyc = LS()
        xyc.append(_xyc)
    ans = 0
    for off_x in range(0, 3):
        for off_y in range(0, 3):
            for off_c in ['B', 'W']:
                cnt = 0
                for x, y, c in xyc:
                    if not valid_board(off_x, off_y, off_c, int(x), int(y), c):
                        continue
                    cnt += 1
                ans = max(ans, cnt)
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
N, K, *L = open(0).read().split()
N = int(N)
K = int(K)
bsheet = [[0]*(2*K) for i in range(2*K)]
wsheet = [[0]*(2*K) for i in range(2*K)]
for x,y,c in zip(*[iter(L)]*3):
  x = int(x)
  y = int(y)
  if c=='W':
    wsheet[x%(2*K)][y%(2*K)] +=1
  else:
    bsheet[x%(2*K)][y%(2*K)] += 1
b_sum = [[0]*(4*K+1) for i in range(4*K+1)]
w_sum = [[0]*(4*K+1) for i in range(4*K+1)]
for i in range(4*K):
  for j in range(4*K):
    si = i
    sj = j
    if si>=2*K:
      si -= 2*K
    if sj>=2*K:
      sj -= 2*K
    b_sum[i+1][j+1] = b_sum[i][j+1]+b_sum[i+1][j]-b_sum[i][j]+bsheet[si][sj]
    w_sum[i+1][j+1] = w_sum[i][j+1]+w_sum[i+1][j]-w_sum[i][j]+wsheet[si][sj]
ans = 0
for i in range(2*K):
  for j in range(2*K):
    bn = (b_sum[2*K+i][2+K+j] - b_sum[K+i][2*K+j] - b_sum[2*K+i][K+j] + 2*b_sum[K+i][K+j]
          - b_sum[K+i][j] - b_sum[i][K+j] + b_sum[i][j])
    
    wn = (w_sum[K+i][2*K+j]+w_sum[2*K+i][K+j]-2*w_sum[K+i][K+j]
    - w_sum[i][2*K+j] + w_sum[i][K+j] - w_sum[2*K+i][j] + w_sum[K+i][j] - w_sum[i][j])
    
    ans = max(ans, bn+wn)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
bsheet = [[0]*(2*K) for i in range(2*K)]
wsheet = [[0]*(2*K) for i in range(2*K)]
for i in range(N):
  x, y, c = input().split()
  x = int(x)
  y = int(y)
  if c=='W':
    wsheet[x%(2*K)][y%(2*K)] +=1
  else:
    bsheet[x%(2*K)][y%(2*K)] += 1
b_sum = [[0]*(4*K+1) for i in range(4*K+1)]
w_sum = [[0]*(4*K+1) for i in range(4*K+1)]
for i in range(4*K):
  for j in range(4*K):
    si = i
    sj = j
    if si>=2*K:
      si -= 2*K
    if sj>=2*K:
      sj -= 2*K
    b_sum[i+1][j+1] = b_sum[i][j+1]+b_sum[i+1][j]-b_sum[i][j]+bsheet[si][sj]
    w_sum[i+1][j+1] = w_sum[i][j+1]+w_sum[i+1][j]-w_sum[i][j]+wsheet[si][sj]
ans = 0
for i in range(2*K):
  for j in range(2*K):
    bn = (b_sum[2*K+i][2+K+j] - b_sum[K+i][2*K+j] - b_sum[2*K+i][K+j] + 2*b_sum[K+i][K+j]
          - b_sum[K+i][j] - b_sum[i][K+j] + b_sum[i][j])
    
    wn = (w_sum[K+i][2*K+j]+w_sum[2*K+i][K+j]-2*w_sum[K+i][K+j]
    - w_sum[i][2*K+j] + w_sum[i][K+j] - w_sum[2*K+i][j] + w_sum[K+i][j] - w_sum[i][j])
    
    ans = max(ans, bn+wn)
print(ans)

Submission status: Wrong Answer

Solution code:
#[0,0]が白い一辺Kの四角の左下隅にあるとして，全部の希望ますが，市松模様のどの位置にいるか調べる？
#各希望マスに関して，[0,0]がどの範囲で動いても大丈夫かを調べる（グリッドが固定されているイメージ？）
#2次元累積和

import sys
input = sys.stdin.readline

N,K=map(int,input().split())
S=[[0]*(2*K+1) for _ in range(2*K+1)]


#スタート位置9箇所
dx=[0,0,K,2*K,K,0,-K,-2*K,-K]
dy=[0,2*K,K,0,-K,-2*K,-K,0,K]

#点aが(2K-1)の正方形の中にあるか?
def ch(a):
    ax=a[1]
    ay=a[0]
    if 0<=ax and ax<=2*K-1:
        if 0<=ay and ay<=2*K-1:
            return True
    return False

#4点a,b,c,dのいずれかは正方形内にある？
def ch4(a,b,c,d):
    Li=[a,b,c,d]
    for i in range(4):
        if ch(Li[i]):
            return True
    return False

#最小を0，最大を2K-1に丸める．
def app(a):
    aa=[0,0]
    for i in range(2):
        aa[i]=a[i]
        if aa[i]<0:
            aa[i]=0
        elif aa[i]>2*K-1:
            aa[i]=2*K-1
    return aa
    
#点aに対応するところにbwを与える
def paint(a,bw):
    S[a[0]][a[1]]+=bw
    return 0
    
    
    


for _ in range(N):
    sx,sy,sc=input().split()
    x=int(sx)%(2*K)
    y=int(sy)%(2*K)
    if sc=="W":
        bw=1
    else:
        bw=-1#該当箇所を-1する
        
    #スタート位置8箇所
    s=(x-(K-1),y-(K-1))
    for i in range(9):
        ld=[s[0]+dy[i],s[1]+dx[i]]#左下
        ru=[ld[0]+(K-1),ld[1]+(K-1)]#右上
        lu=[ru[0],ld[1]]
        rd=[ld[0],ru[1]]
        
        if ch4(ld,ru,lu,rd):#4点のどれかが正方形内なら
            ld=app(ld)
            ru=app(ru)
            ru[0]+=1#累積和で-1するところは領域外（1つ奥のところ）
            ru[1]+=1
            lu=[ru[0],ld[1]]
            rd=[ld[0],ru[1]]
            paint(ld,bw)
            paint(ru,bw)
            paint(lu,bw*-1)
            paint(rd,bw*-1)
            
    if bw==-1:#該当箇所が-1されているので，全部を+1する
        S[0][0]+=1
        S[-1][-1]+=1
        S[0][-1]-=1
        S[-1][0]-=1
            
            

#累積    
for i in range(2*K+1):
    for j in range(2*K):
        S[i][j+1]+=S[i][j]
        
for j in range(2*K+1):
    for i in range(2*K):
        S[i+1][j]+=S[i][j]
        
        
ans=0
for i in range(2*K+1):
    for j in range(2*K+1):
        if S[i][j]>ans:
            ans=S[i][j]
          
        
print(ans)

Submission status: Wrong Answer

Solution code:
#[0,0]が白い一辺Kの四角の左下隅にあるとして，全部の希望ますが，市松模様のどの位置にいるか調べる？
#各希望マスに関して，[0,0]がどの範囲で動いても大丈夫かを調べる（グリッドが固定されているイメージ？）
#2次元累積和

import sys
input = sys.stdin.readline

N,K=map(int,input().split())
S=[[0]*(2*K+1) for _ in range(2*K+1)]


#スタート位置9箇所
dx=[0,0,K,2*K,K,0,-K,-2*K,-K]
dy=[0,2*K,K,0,-K,-2*K,-K,0,K]

#最小を0，最大を2Kに丸める．
def app(a):
    aa=[0,0]
    for i in range(2):
        aa[i]=a[i]
        if aa[i]<0:
            aa[i]=0
        elif aa[i]>2*K:
            aa[i]=2*K
    return aa
    
#点aに対応するところにbwを与える
def paint(a,bw):
    S[a[0]][a[1]]+=bw
    return 0
    
    
    


for _ in range(N):
    sx,sy,sc=input().split()
    x=int(sx)%(2*K)
    y=int(sy)%(2*K)
    if sc=="W":
        bw=1
    else:
        bw=-1#該当箇所を-1する
        
    #スタート位置9箇所
    s=(x-(K-1),y-(K-1))
    for i in range(9):
        #4点全てが範囲外でも，丸めているので累積和への効果はない
        ld=[s[0]+dy[i],s[1]+dx[i]]#左下
        ru=[ld[0]+K,ld[1]+K]#右上，累積和で-1するところは領域外（1つ奥のところ)
        ld=app(ld)
        ru=app(ru)
        
        lu=[ru[0],ld[1]]
        rd=[ld[0],ru[1]]
        
        paint(ld,bw)
        paint(ru,bw)
        paint(lu,bw*-1)
        paint(rd,bw*-1)
            
    if bw==-1:#該当箇所が-1されているので，全部を+1する
        S[0][0]+=1
        S[-1][-1]+=1
        S[0][-1]-=1
        S[-1][0]-=1
            
            

#累積    
for i in range(2*K+1):
    for j in range(2*K):
        S[i][j+1]+=S[i][j]
        
for j in range(2*K+1):
    for i in range(2*K):
        S[i+1][j]+=S[i][j]
        
        
ans=0
for i in range(2*K+1):
    for j in range(2*K+1):
        if S[i][j]>ans:
            ans=S[i][j]
          
        
print(ans)

Submission status: Wrong Answer

Solution code:
#[0,0]が白い一辺Kの四角の左下隅にあるとして，全部の希望ますが，市松模様のどの位置にいるか調べる？
#各希望マスに関して，[0,0]がどの範囲で動いても大丈夫かを調べる（グリッドが固定されているイメージ？）
#2次元累積和

N,K=map(int,input().split())
S=[[0]*(2*K+1) for _ in range(2*K+1)]


#スタート位置9箇所
dx=[0,0,K,2*K,K,0,-K,-2*K,-K]
dy=[0,2*K,K,0,-K,-2*K,-K,0,K]

#点aが(2K-1)の正方形の中にあるか?
def ch(a):
    ax=a[1]
    ay=a[0]
    if 0<=ax and ax<=2*K-1:
        if 0<=ay and ay<=2*K-1:
            return True
    return False

#2点a,bのいずれかは正方形内にある？
def ch2(a,b):
    if ch(a):
        return True
    if ch(b):
        return True
    return False

#最小を0，最大を2K-1に丸める．
def app(a):
    aa=[0,0]
    for i in range(2):
        aa[i]=a[i]
        if aa[i]<0:
            aa[i]=0
        elif aa[i]>2*K-1:
            aa[i]=2*K-1
    return aa
    
#点aに対応するところにbwを与える
def paint(a,bw):
    S[a[0]][a[1]]+=bw
    return 0
    
    
    


for _ in range(N):
    sx,sy,sc=input().split()
    x=int(sx)%(2*K)
    y=int(sy)%(2*K)
    if sc=="W":
        bw=1
    else:
        bw=-1#該当箇所を-1する
        
    #スタート位置8箇所
    s=(x-(K-1),y-(K-1))
    for i in range(9):
        ld=[s[0]+dy[i],s[1]+dx[i]]#左下
        ru=[ld[0]+(K-1),ld[1]+(K-1)]#右上
        
        if ch2(ld,ru):#どちらかが正方形内なら
            ld=app(ld)
            ru=app(ru)
            ru[0]+=1#累積和で-1するところは+1が必要
            ru[1]+=1
            lu=[ru[0],ld[1]]
            rd=[ld[0],ru[1]]
            paint(ld,bw)
            paint(ru,bw)
            paint(lu,bw*-1)
            paint(rd,bw*-1)
            
    if bw==-1:#該当箇所が-1されているので，全部を+1する
        S[0][0]+=1
        S[-1][-1]+=1
        S[0][-1]-=1
        S[-1][0]-=1
            
            

#累積    
for i in range(2*K+1):
    for j in range(2*K):
        S[i][j+1]+=S[i][j]
        
for j in range(2*K+1):
    for i in range(2*K):
        S[i+1][j]+=S[i][j]
        
        
ans=0
for i in range(2*K+1):
    for j in range(2*K+1):
        if S[i][j]>ans:
            ans=S[i][j]
          
        
print(ans)

Submission status: Wrong Answer

Solution code:
#[0,0]が白い一辺Kの四角の左下隅にあるとして，全部の希望ますが，市松模様のどの位置にいるか調べる？
#各希望マスに関して，[0,0]がどの範囲で動いても大丈夫かを調べる（グリッドが固定されているイメージ？）
#2次元累積和

N,K=map(int,input().split())
S=[[0]*(2*K+1) for _ in range(2*K+1)]


#スタート位置9箇所
dx=[0,0,K,2*K,K,0,-K,-2*K,-K]
dy=[0,2*K,K,0,-K,-2*K,-K,0,K]

#点aが(2K-1)の正方形の中にあるか?
def ch(a):
    ax=a[1]
    ay=a[0]
    if 0<=ax and ax<=2*K-1:
        if 0<=ay and ay<=2*K-1:
            return True
    return False

#2点a,bのいずれかは正方形内にある？
def ch2(a,b):
    if ch(a):
        return True
    if ch(b):
        return True
    return False

#最小を0，最大を2K-1に丸める．
def app(a):
    aa=[0,0]
    for i in range(2):
        aa[i]=a[i]
        if aa[i]<0:
            aa[i]=0
        elif aa[i]>2*K-1:
            aa[i]=2*K-1
    return aa
    
#点aに対応するところにbwを与える
def paint(a,bw):
    S[a[0]][a[1]]+=bw
    return 0
    
    
    


for _ in range(N):
    sx,sy,sc=input().split()
    x=int(sx)%(2*K)
    y=int(sy)%(2*K)
    if sc=="W":
        bw=1
    else:
        bw=-1#該当箇所を-1する
        
    #スタート位置8箇所
    s=(x-(K-1),y-(K-1))
    for i in range(9):
        ld=[s[0]+dy[i],s[1]+dx[i]]#左下
        ru=[ld[0]+(K-1),ld[1]+(K-1)]#右上
        
        if ch2(ld,ru):#どちらかが正方形内なら
            ld=app(ld)
            ru=app(ru)
            ru[0]+=1
            ru[1]+=1
            lu=[ru[0],ld[1]]
            rd=[ld[0],ru[1]]
            paint(ld,bw)
            paint(ru,bw)
            paint(lu,bw*-1)
            paint(rd,bw*-1)
            
    if bw==-1:#該当箇所が-1されているので，全部を+1する
        S[0][0]+=1
        S[-1][-1]+=1
        S[0][-1]-=1
        S[-1][0]-=1
            
            

#累積    
for i in range(2*K+1):
    for j in range(2*K):
        S[i][j+1]+=S[i][j]
        
for j in range(2*K+1):
    for i in range(2*K):
        S[i+1][j]+=S[i][j]
        
        
ans=0
for i in range(2*K):
    for j in range(2*K):
        if S[i][j]>ans:
            ans=S[i][j]
          
        
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy
#input()
N,K=map(int,input().split())
XYC=[input().split() for i in range(N)]
for i in range(N):
    x,y,c=XYC[i]
    XYC[i]=[int(x),int(y),c]

lstB=[[0 for i in range(K)] for m in range(K)]
lstW=[[0 for i in range(K)] for m in range(K)]
for x,y,c in XYC:
    if (x//K + y//K + (c=="W") * 1)%2==0:
        lstW[x%K][y%K]+=1
    else:
        lstB[x%K][y%K]+=1

sumB=[sum(lstB[x]) for x in range(K)]
sumW=[sum(lstW[x]) for x in range(K)]
ruisumB=[0]
ruisumW=[0]
for i in range(0,K):
    ruisumB.append(ruisumB[i]+sumB[i])
    ruisumW.append(ruisumW[i]+sumW[i])


ruiBy=[[0] for k in range(K)]
ruiWy=[[0] for k in range(K)]
for y in range(K):
    for x in range(K):
        ruiBy[y].append(lstB[x][y]+ruiBy[y][x])
        ruiWy[y].append(lstW[x][y]+ruiWy[y][x])
Revalue=0
for x in range(K+1):
    value=0
    value+=ruisumW[x]
    value+=ruisumB[K]-ruisumB[x]
    Revalue=max(Revalue,value)
    for y in range(K):
        value+=ruiWy[y][K]-2*ruiWy[y][x]
        value-=ruiBy[y][K]-2*ruiBy[y][x]
        Revalue=max(Revalue,value)

print(Revalue)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy
#input()
N,K=map(int,input().split())
XYC=[input().split() for i in range(N)]
for i in range(N):
    x,y,c=XYC[i]
    XYC[i]=[int(x),int(y),c]

lstB=[[0 for i in range(K)] for m in range(K)]
lstW=[[0 for i in range(K)] for m in range(K)]
for x,y,c in XYC:
    if (x//K + y//K + (c=="W") * 1)%2:
        lstW[x%K][y%K]+=1
    else:
        lstB[x%K][y%K]+=1

sumB=[sum(lstB[x]) for x in range(K)]
sumW=[sum(lstW[x]) for x in range(K)]
ruisumB=[0]
ruisumW=[0]
for i in range(0,K):
    ruisumB.append(ruisumB[i]+sumB[i])
    ruisumW.append(ruisumW[i]+sumW[i])


ruiBy=[[0] for k in range(K)]
ruiWy=[[0] for k in range(K)]
for y in range(K):
    for x in range(K):
        ruiBy[y].append(lstB[x][y]+ruiBy[y][x])
        ruiWy[y].append(lstW[x][y]+ruiWy[y][x])
Revalue=0
for x in range(K+1):
    value=0
    value+=ruisumW[x]
    value+=ruisumB[K]-ruisumB[x]
    Revalue=max(Revalue,value)
    for y in range(K):
        value+=ruiWy[y][K]-2*ruiWy[y][x]
        value-=ruiBy[y][K]-2*ruiBy[y][x]
        Revalue=max(Revalue,value)

if Revalue>N:
    print(Unko)
print(Revalue)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy
#input()
N,K=map(int,input().split())
XYC=[input().split() for i in range(N)]
for i in range(N):
    x,y,c=XYC[i]
    XYC[i]=[int(x),int(y),c]

lstB=[[0 for i in range(K)] for m in range(K)]
lstW=[[0 for i in range(K)] for m in range(K)]
for x,y,c in XYC:
    if (x//K + y//K + (c=="W") * 1)%2:
        lstB[x%K][y%K]+=1
    else:
        lstW[x%K][y%K]+=1

sumB=[sum(lstB[x]) for x in range(K)]
sumW=[sum(lstW[x]) for x in range(K)]
ruisumB=[0]
ruisumW=[0]
for i in range(0,K):
    ruisumB.append(ruisumB[i]+sumB[i])
    ruisumW.append(ruisumW[i]+sumW[i])


ruiBy=[[0] for k in range(K)]
ruiWy=[[0] for k in range(K)]
for y in range(K):
    for x in range(K):
        ruiBy[y].append(lstB[x][y]+ruiBy[y][x])
        ruiWy[y].append(lstW[x][y]+ruiWy[y][x])
Revalue=0
for x in range(K+1):
    value=0
    value+=ruisumW[x]
    value+=ruisumB[K]-ruisumB[x]
    Revalue=max(Revalue,value)
    for y in range(K):
        value+=ruiWy[y][K]-2*ruiWy[y][x]
        value-=ruiBy[y][K]-2*ruiBy[y][x]
        Revalue=max(Revalue,value)

print(Revalue)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy
#input()
N,K=map(int,input().split())
XYC=[input().split() for i in range(N)]
for i in range(N):
    x,y,c=XYC[i]
    XYC[i]=[int(x),int(y),c]

lstB=[[0 for i in range(K)] for m in range(K)]
lstW=[[0 for i in range(K)] for m in range(K)]
for x,y,c in XYC:
    if (x//K + y//K + (c=="W") * 1)%2:
        lstB[x%K][y%K]+=1
    else:
        lstW[x%K][y%K]+=1

sumB=[sum(lstB[x]) for x in range(K)]
sumW=[sum(lstW[x]) for x in range(K)]
ruisumB=[0]
ruisumW=[0]
for i in range(0,K):
    ruisumB.append(ruisumB[i]+sumB[i])
    ruisumW.append(ruisumW[i]+sumW[i])
"""
print(sumB)
print(ruisumB)
print(sumW)
print(ruisumW)
"""

ruiBy=[[0] for k in range(K)]
ruiWy=[[0] for k in range(K)]
for y in range(K):
    for x in range(K):
        ruiBy[y].append(lstB[x][y]+ruiBy[y][x])
        ruiWy[y].append(lstW[x][y]+ruiWy[y][x])
"""
ruiBx=[[lstB[x][0]] for x in range(K)]
ruiWx=[[lstW[x][0]] for x in range(K)]

for y in range(1,K):
    for x in range(K):
        ruiBx[x].append(lstB[x][y]+ruiBx[x][y-1])
        ruiWx[x].append(ruiW[x][y]+ruiWx[x][y-1])
"""
Revalue=0
for x in range(K+1):
    value=0
    value+=ruisumW[x]
    value+=ruisumB[K]-ruisumB[x]
    Revalue=max(Revalue,value)
    for y in range(K):
        value+=ruiWy[y][K]-2*ruiWy[y][x]
        value-=ruiBy[y][K]-2*ruiBy[y][x]
        Revalue=max(Revalue,value)

print(Revalue)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from collections import Counter

read = sys.stdin

N, K = map(int, read.readline().split())
k = 2 * K
xyc = np.array(read.read().split(), np.str).reshape(-1, 3)
x = xyc[:, 0].astype(int)
y = xyc[:, 1].astype(int)
c = xyc[:, 2]

x = np.where(c == 'B', x - K, x)
x %= k
y %= k

'''
# grid[[1,2],[1,2]]+=1 としてもgrid[1,2]=1であり重複は考慮されない。
# uniqueを使って(x,y)の重複をカウントする
# return_countはver1.9からだった・・・ ダメじゃん
xy, cnt = np.unique(x + y * 10000, return_counts=True)
x = xy % 10000
y = xy // 10000
'''
xy = Counter(list(zip(x, y)))
cnt = np.array(list(xy.values()), np.int64)
xy = np.array(list(xy.keys()), np.int64)
x = xy[:, 0]
y = xy[:, 1]

grid = np.zeros((3 * K, 3 * K), np.int64)
grid[x, y] += cnt
grid[x + K, y + K] += cnt
grid[x + K, y] -= cnt
grid[x, y + K] -= cnt
np.cumsum(grid, axis=0, out=grid)
np.cumsum(grid, axis=1, out=grid)

answer = grid[:K, :K] + grid[k:, k:] + grid[K:k, K:k] + grid[k:, :K] + grid[:K, k:]
print(answer.max())

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

read = sys.stdin

N, K = map(int, read.readline().split())
k = 2 * K
xyc = np.array(read.read().split(), np.str).reshape(-1, 3)
x = xyc[:, 0].astype(np.int64)
y = xyc[:, 1].astype(np.int64)
c = xyc[:, 2]

y = np.where(c == 'W', y + K, y)
x %= k
y %= k

grid = np.zeros((3 * K, 3 * K), np.int64)
grid[x, y] += 1
grid[x + K, y + K] += 1
grid[x + K, y] -= 1
grid[x, y + K] -= 1
np.cumsum(grid, axis=0, out=grid)
np.cumsum(grid, axis=1, out=grid)

p1 = grid[:K, :K] + grid[k:, k:] + grid[K:k, K:k] + grid[k:, :K] + grid[:K, k:]
p2 = grid[K:k, :K] + grid[K:k, k:] + grid[:K, K:k] + grid[k:, K:k]
print(max(p1.max(), p2.max()))

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

read = sys.stdin

N, K = map(int, read.readline().split())
k = 2 * K
xyc = np.array(read.read().split(), np.str).reshape(-1, 3)
x = xyc[:, 0].astype(int)
y = xyc[:, 1].astype(int)
c = xyc[:, 2]

y = np.where(c == 'W', y + K, y)
x %= k
y %= k

grid = np.zeros((3 * K, 3 * K), np.int64)
grid[x, y] += 1
grid[x + K, y + K] += 1
grid[x + K, y] -= 1
grid[x, y + K] -= 1
np.cumsum(grid, axis=0, out=grid)
np.cumsum(grid, axis=1, out=grid)

p1 = grid[:K, :K] + grid[k:, k:] + grid[K:k, K:k] + grid[k:, :K] + grid[:K, k:]
p2 = grid[K:k, :K] + grid[K:k, k:] + grid[:K, K:k] + grid[k:, K:k]
print(max(p1.max(), p2.max()))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
ps = []
table = [[0] * (2 * K) for _ in range(2 * K)]
res = 0
for i in range(N):
  u, v, t = input().split()
  u = int(u)
  v = int(v)
  ps.append((u % (2 * K), v % (2 * K), t))
  table[(u + (K * (t == "W"))) % (2 * K)][v % (2 * K)] += 1
  if t == "B": continue
  table[u % (2 * K)][(v + (K * (t == "W"))) % (2 * K)] += 1
cs = [[0] * (2 * K + 1) for _ in range(2 * K)]
for i in range(2 * K):
  for j in range(2 * K): cs[i][j + 1] = cs[i][j] + table[i][j]

for i in range(2 * K):
  t = 0
  tres = 0
  for j in range(K): t += cs[j][min(2 * K, i + K)] + cs[j][max(0, i - K)] - cs[j][i] 
  tres = max(tres, t)
  for j in range(2 * K):
    t -= cs[j][min(2 * K, i + K)] + cs[j][max(0, i - K)] - cs[j][i]
    t += cs[(j + K) % (2 * K)][min(2 * K, i + K)] + cs[(j + K) % (2 * K)][max(0, i - K)] - cs[(j + K) % (2 * K)][i]
    tres = max(tres, t)
    #print(tres, t, i, j + 1, j + K)
  res = max(res, tres)
print(res)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
g = [[0]*(k+1) for _ in range(k+1)]
ans,b = 0,0
for _ in range(n):
  x,y,c = input().split()
  x,y = int(x), int(y)
  d = x//k + y//k
  x %= k; y %= k
  if (c == 'W') ^ (d%2):
    g[x+1][y+1] += 1
  else:
    g[x+1][y+1] -= 1
    b += 1
for i in range(k):
  for j in range(k):
    g[i+1][j+1] += g[i][j+1] + g[i+1][j] - g[i][j]
for i in range(k):
  for j in range(k):
    cur = g[k][k] - g[k][j] - g[i][k] + g[i][j]*2 + b
    if cur > ans: ans = cur
    elif n-cur > ans: ans = n-cur
print(ans)