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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

#############
# Main Code #
#############

N,K = IL()
data = SLL(N)

B_data = [[0 for i in range(2*K)] for i in range(2*K)]
W_data = [[0 for i in range(2*K)] for i in range(2*K)]

for x,y,c in data:
  x,y = int(x)%(2*K),int(y)%(2*K)
  if c == "B":
    B_data[y][x] += 1
  else:
    W_data[y][x] += 1

def ACC2(l):
  H = len(l)
  W = len(l[0])
  ret = [[0]*(W+1) for i in range(H+1)]
  for i in range(H):
    for j in range(W):
      ret[i+1][j+1] = ret[i+1][j] + ret[i][j+1] - ret[i][j] + l[i][j]
  return ret

def RANGE_SUM_in_ACC(l,h1,h2,w1,w2):
  return l[h2][w2]-l[h2][w1]-l[h1][w2]+l[h1][w1]

B_ACC = ACC2(B_data)
W_ACC = ACC2(W_data)
del(B_data)
del(W_data)
B_res = [[0 for i in range(2*K)] for i in range(K)]
W_res = [[0 for i in range(2*K)] for i in range(K)]

for j in range(K):
  for i in range(2*K):
    if i<K:
      B_res[j][i] += RANGE_SUM_in_ACC(B_ACC,j,j+K,i,i+K)
      B_res[j][i] += RANGE_SUM_in_ACC(B_ACC,0,max(0,j-1),0,max(0,i-1))
      B_res[j][i] += RANGE_SUM_in_ACC(B_ACC,0,max(0,j-1),min(2*K,i+K),2*K)
      B_res[j][i] += RANGE_SUM_in_ACC(B_ACC,min(2*K,j+K),2*K,0,max(0,i-1))
      B_res[j][i] += RANGE_SUM_in_ACC(B_ACC,min(2*K,j+K),2*K,min(2*K,i+K),2*K)
      W_res[j][i] += RANGE_SUM_in_ACC(W_ACC,j,j+K,i,i+K)
      W_res[j][i] += RANGE_SUM_in_ACC(W_ACC,0,max(0,j-1),0,max(0,i-1))
      W_res[j][i] += RANGE_SUM_in_ACC(W_ACC,0,max(0,j-1),min(2*K,i+K),2*K)
      W_res[j][i] += RANGE_SUM_in_ACC(W_ACC,min(2*K,j+K),2*K,0,max(0,i-1))
      W_res[j][i] += RANGE_SUM_in_ACC(W_ACC,min(2*K,j+K),2*K,min(2*K,i+K),2*K)
    else:
      B_res[j][i] = B_ACC[-1][-1]-B_res[j][i-K]
      W_res[j][i] = W_ACC[-1][-1]-W_res[j][i-K]
      
ans = 0
for j in range(K):
  for i in range(2*K):
    ans = max(ans,B_res[j][i]+W_res[j][i])
print(ans)

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,K = IL()
data = SLL(N)

B_data = [[0 for i in range(2*K)] for i in range(2*K)]
W_data = [[0 for i in range(2*K)] for i in range(2*K)]

for x,y,c in data:
  x,y = int(x)%(2*K),int(y)%(2*K)
  if c == "B":
    B_data[y][x] += 1
  else:
    W_data[y][x] += 1

def ACC2(l):
  H = len(l)
  W = len(l[0])
  ret = [[0]*(W+1) for i in range(H+1)]
  for i in range(H):
    for j in range(W):
      ret[i+1][j+1] = ret[i+1][j] + ret[i][j+1] - ret[i][j] + l[i][j]
  return ret

def RANGE_SUM_in_ACC(l,h1,h2,w1,w2):
  return l[h2][w2]-l[h2][w1]-l[h1][w2]+l[h1][w1]

B_ACC = ACC2(B_data)
W_ACC = ACC2(W_data)

B_res = [[0 for i in range(2*K)] for i in range(K)]
W_res = [[0 for i in range(2*K)] for i in range(K)]

for j in range(K):
  for i in range(2*K):
    if i<K:
      B_res[j][i] += RANGE_SUM_in_ACC(B_ACC,j,j+K,i,i+K)
      B_res[j][i] += RANGE_SUM_in_ACC(B_ACC,0,max(0,j-1),0,max(0,i-1))
      B_res[j][i] += RANGE_SUM_in_ACC(B_ACC,0,max(0,j-1),min(2*K,i+K),2*K)
      B_res[j][i] += RANGE_SUM_in_ACC(B_ACC,min(2*K,j+K),2*K,0,max(0,i-1))
      B_res[j][i] += RANGE_SUM_in_ACC(B_ACC,min(2*K,j+K),2*K,min(2*K,i+K),2*K)
      W_res[j][i] += RANGE_SUM_in_ACC(W_ACC,j,j+K,i,i+K)
      W_res[j][i] += RANGE_SUM_in_ACC(W_ACC,0,max(0,j-1),0,max(0,i-1))
      W_res[j][i] += RANGE_SUM_in_ACC(W_ACC,0,max(0,j-1),min(2*K,i+K),2*K)
      W_res[j][i] += RANGE_SUM_in_ACC(W_ACC,min(2*K,j+K),2*K,0,max(0,i-1))
      W_res[j][i] += RANGE_SUM_in_ACC(W_ACC,min(2*K,j+K),2*K,min(2*K,i+K),2*K)
    else:
      B_res[j][i] = B_ACC[-1][-1]-B_res[j][i-K]
      W_res[j][i] = W_ACC[-1][-1]-W_res[j][i-K]
      
ans = 0
for j in range(K):
  for i in range(2*K):
    ans = max(ans,B_res[j][i]+W_res[j][i])
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
import numpy as np
#対称性を利用して点を単位格子K*2Kに圧縮
_2K, _4K = 2*K, 4*K
shape = (_2K+1,_4K+1) #後でK*2Kに圧縮
Grd = np.zeros(shape,dtype='int64')
for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'B':
        x, y = x%_2K, y%_2K
    else: 
        x, y = (x+K)%_2K, y%_2K
    #点について、2K*2K -> K*2Kの調整。次は等価、(K+i,K+j)==(i,j),(i,K+j)==(i+K,j)
    if x >= K and y >= K: x -= K; y -= K
    if x < K and y >= K: x += K; y -= K
    #この点がK*Kの黒色正方形内に入る。正方形を特徴づけるには左下の座標だけで十分。
    #⇒１つの点はK**2個の塗り方に+1の影響を与える。
    #毎回2K**2のマスにアクセスするとTLEするため、あとで累積和(計算量O(K**2))を取った時に+1される範囲が等しくなるように調整する(隣接差分を取る)。
    #K=3の場合
    #[[1 1 1 0 0 0]    [[ 1 0 0 -1 0 0  0]
    # [1 1 1 0 0 0]     [ 0 0 0  0 0 0  0]
    # [1 1 1 0 0 0]  => [ 0 0 0  0 0 0  0]
    # [0 0 0 0 0 0]     [-1 0 0  1 0 0  0]
    # [0 0 0 0 0 0]     [ 0 0 0  0 0 0  0]
    # [0 0 0 0 0 0]]    [ 0 0 0  0 0 0  0]
    #                   [ 0 0 0  0 0 0  0]
    
    Grd[y, x] += 1
    Grd[y+K, x+K] += 1
    Grd[y+K, x] += -1
    Grd[y, x+K] += -1
del x, y, c

#2重累積和計算
Grd = Grd.cumsum().reshape(shape).T.cumsum().reshape(shape)
#2K*4K -> K*2Kへ圧縮
#Grd = Grd[:K,:_2K] +Grd[:K,_2K:_4K] +Grd[K:_2K,:_2K] +Grd[K:_2K,_2K:_4K]

ans = Grd.max()
print(ans)

Submission status: Wrong Answer

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

# あとで開区間な累積和を取るので、K+1。
want_white = [[0] * (K+1) for _ in range(K+1)]
want_black = [[0] * (K+1) for _ in range(K+1)]

for _ in range(N):
    x_str, y_str, c_str = input().split()
    x = int(x_str)
    y = int(y_str)
    c = 1 if c_str == 'B' else 0

    x %= 2 * K
    y %= 2 * K
    if x >= K:
        x -= K
        c ^= 1
    if y >= K:
        y -= K
        c ^= 1

    if c:
        want_black[x+1][y+1] += 1
    else:
        want_white[x+1][y+1] += 1

# 累積和
for i in range(K+1):
    for j in range(K):
        want_black[i][j+1] += want_black[i][j]
        want_white[i][j+1] += want_white[i][j]

for i in range(K):
    for j in range(K+1):
        want_black[i+1][j] += want_black[i][j]
        want_white[i+1][j] += want_white[i][j]

# (h, w)が黒の左下になるとして、全探索。
ans = 0
for h in range(K):
    for w in range(K):
        count = want_black[-1][-1] - want_black[h][-1] - want_black[-1][w] + 2 * want_black[h][w]
        assert count >= 0
        assert  want_white[h][-1] + want_white[-1][w] - 2 * want_white[h][w] >= 0
        count += want_white[h][-1] + want_white[-1][w] - 2 * want_white[h][w]
        ans = max(ans, count)

print(ans)

Submission status: Wrong Answer

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

# あとで開区間な累積和を取るので、K+1。
want_white = [[0] * (K+1) for _ in range(K+1)]
want_black = [[0] * (K+1) for _ in range(K+1)]

for _ in range(N):
    x_str, y_str, c = input().split()
    x = int(x_str)
    y = int(y_str)
    c = 1 if c == 'B' else 0

    x %= 2 * K
    y %= 2 * K
    if x >= K:
        x -= K
        c ^= 1
    if y >= K:
        y -= K
        c ^= 1

    if c:
        want_black[x+1][y+1] += 1
    else:
        want_white[x+1][y+1] += 1

# 累積和
for i in range(K+1):
    for j in range(K):
        want_black[i][j+1] += want_black[i][j]
        want_white[i][j+1] += want_white[i][j]

for i in range(K):
    for j in range(K+1):
        want_black[i+1][j] += want_black[i][j]
        want_white[i+1][j] += want_white[i][j]

# (h, w)が黒の左下になるとして、全探索。
ans = 0
for h in range(K+1):
    for w in range(K+1):
        count = want_black[-1][-1] - want_black[h][-1] - want_black[-1][w] + 2 * want_black[h][w]
        count += want_white[h][-1] + want_white[-1][w] - 2 * want_white[h][w]
        ans = max(ans, count)
        
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n, k = map(int, input().split())
m = 2*k
G = [[0]*m for _ in range(m)]
def f(x, y):
  G[x][y] += 1
  G[(x+k)%m][y] -= 1
  G[x][(y+k)%m] -= 1
  G[(x+k)%m][(y+k)%m] += 1
for _ in range(n):
  x, y, c = input().split()
  x = int(x)%m
  y = int(y)%m
  if c == "W":
    x += k
    x %= m
  f(x, y)
  f((x+k)%m, (y+k)%m)
for i in range(m):
  G[i] = list(accumulate(G[i]))
ans = 0
G = zip(*G)
for g in G:
  ans = max(ans, max(accumulate(g)))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n, k = map(int, input().split())
m = 2*k
G = [[0]*(3*k) for _ in range(3*k)]
for _ in range(n):
  x, y, c = input().split()
  x = int(x)%m
  y = int(y)%m
  if c == "W":
    x += k
    x %= m
  if x >= k and y >= k:
    x -= k
    y -= k
  G[x][y] += 1
  G[x+k][y] -= 1
  G[x][y+k] -= 1
  G[x+k][y+k] -= 1
for i in range(3*k):
  G[i] = list(accumulate(G[i]))
ans = 0
G = zip(*G)
for g in G:
  ans = max(ans, max(accumulate(g)))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n, k = map(int, input().split())
m = 2*k
G = [[0]*(3*k) for _ in range(3*k)]
for _ in range(n):
  x, y, c = input().split()
  x = int(x)%m
  y = int(y)%m
  if c == "W":
    x += k
    x %= m
  G[x][y] += 1
  G[x+k][y] -= 1
  G[x][y+k] -= 1
  G[x+k][y+k] -= 1
for i in range(3*k):
  G[i] = list(accumulate(G[i]))
ans = 0
G = zip(*G)
for g in G:
  ans = max(ans, max(accumulate(g)))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n, k = map(int, input().split())
m = 2*k
G = [[0]*(2*m) for _ in range(2*m)]
for _ in range(n):
  x, y, c = input().split()
  x = int(x)%m
  y = int(y)%m
  if c == "W":
    G[x+k][y] += 1
    G[x+m][y] -= 1
    G[x+k][y+k] -= 1
    G[x+m][y+k] += 1
    G[x][y+k] += 1
    G[x+k][y+k] -= 1
    G[x][y+m] -= 1
    G[x+k][y+m] += 1
  else:
    G[x][y] += 1
    G[x+k][y] -= 1
    G[x][y+k] -= 1
    G[x+k][y+k] += 1
    G[x+k][y+k] += 1
    G[x+m][y+k] -= 1
    G[x+k][y+m] -= 1
    G[x+m][y+m] += 1
for i in range(2*m):
  G[i] = list(accumulate(G[i]))
ans = 0
G = zip(*G)
for g in G:
  ans = max(ans, max(accumulate(g)))
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


n,k=map(int,input().split())
xyc=[list(input().split()) for i in range(n)]

ww=[[0]*(2*k+1) for i in range(2*k+1)]
bb=[[0]*(2*k+1) for i in range(2*k+1)]

for i in range(n):
    x,y,c=xyc[i]
    x,y=int(x),int(y)
    if c=="W":
        ww[x%(2*k)+1][y%(2*k)+1]+=1
    else:
        bb[x%(2*k)+1][y%(2*k)+1]+=1

for i in range(2*k):
    for j in range(2*k):
        ww[i+1][j+1]=ww[i+1][j+1]+ww[i+1][j]+ww[i][j+1]-ww[i][j]
        bb[i+1][j+1]=bb[i+1][j+1]+bb[i+1][j]+bb[i][j+1]-bb[i][j]
# print(ww)

def cnt(i1,i2,j1,j2,lst):
    return lst[i2+1][j2+1]-lst[i1+1][j2+1]-lst[i2+1][j1+1]+lst[i1+1][j1+1]

ans=0
for i in range(k+1):
    for j in range(k+1):
        w,b=0,0
        # 左下
        w+=cnt(-1, i-1, -1, j-1, ww)
        # 中央
        w+=cnt(i-1, i+k-1, j-1, j+k-1, ww)
        # 左上
        w+=cnt(-1, i-1, j+k-1, 2*k-1, ww)
        # 右下
        w+=cnt(i+k-1, 2*k-1, -1, j-1, ww)
        # 右上
        w+=cnt(i+k-1, 2*k-1, j+k-1, 2*k-1, ww)

        b+=cnt(-1, i-1, j-1, j+k-1, bb)
        b+=cnt(i-1, i+k-1, -1, j-1, bb)
        b+=cnt(i+k-1, 2*k-1, j-1, j+k-1, bb)
        b+=cnt(i-1, i+k-1, j+k-1, 2*k-1, bb)
        # print(w,b)
        ans=max(ans,w+b)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


n,k=map(int,input().split())
xyc=[list(input().split()) for i in range(n)]

ww=[[0]*(2*k+1) for i in range(2*k+1)]
bb=[[0]*(2*k+1) for i in range(2*k+1)]

for i in range(n):
    x,y,c=xyc[i]
    x,y=int(x),int(y)
    if c=="W":
        ww[x%(2*k)+1][y%(2*k)+1]+=1
    else:
        bb[x%(2*k)+1][y%(2*k)+1]+=1

for i in range(2*k):
    for j in range(2*k):
        ww[i+1][j+1]=ww[i+1][j+1]+ww[i+1][j]+ww[i][j+1]-ww[i][j]
        bb[i+1][j+1]=bb[i+1][j+1]+bb[i+1][j]+bb[i][j+1]-bb[i][j]
# print(bb)

def cnt(i1,i2,j1,j2,lst):
    return lst[i2+1][j2+1]-lst[i1+1][j2+1]-lst[i2+1][j1+1]+lst[i1+1][j1+1]

ans=0
for i in range(k):
    for j in range(k):
        w,b=0,0
        w+=cnt(-1, i-1, -1, j-1, ww)
        w+=cnt(i-1, i+k-1, j-1, j+k-1, ww)
        w+=cnt(-1, i-1, j+k, 2*k-1, ww)
        w+=cnt(i+k-1, 2*k-1, -1, j-1, ww)
        w+=cnt(i+k-1, 2*k-1, j+k-1, 2*k-1, ww)

        b+=cnt(-1, i-1, j-1, j+k-1, bb)
        b+=cnt(i-1, i+k-1, -1, j-1, bb)
        b+=cnt(i+k-1, 2*k-1, j-1, j+k-1, bb)
        b+=cnt(i-1, i+k-1, j+k-1, 2*k-1, bb)
        ans=max(ans,w+b)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate
input = sys.stdin.readline
N,K = map(int,input().split())
xyc = []
for i in range(N):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    xyc.append([x % (2*K), y % (2*K), c])

wmap = [[0]*4*K for i in [0]*4*K]
hmap = [[0]*4*K for i in [0]*4*K]
for x,y,c in xyc:
    if c == 'W':
        wmap[y][x] += 1
        wmap[y+2*K][x] += 1
        wmap[y][x+2*K] += 1
        wmap[y+2*K][x+2*K] += 1
    else:
        hmap[y][x] += 1
        hmap[y][x+2*K] += 1
        hmap[y+2*K][x] += 1
        hmap[y+2*K][x+2*K] += 1

wcumsum = [[0]*(4*K+1)] + [[0]+list(accumulate(row)) for row in wmap]
hcumsum = [[0]*(4*K+1)] + [[0]+list(accumulate(row)) for row in hmap]
for y in range(1,4*K+1):
    for x in range(4*K+1):
        wcumsum[y][x] += wcumsum[y-1][x]
        hcumsum[y][x] += hcumsum[y-1][x]

def cs2(m, ltx, lty, rbx, rby):
    S = m[rby-1][rbx-1]
    S -= m[rby-1][ltx-1]
    S -= m[lty-1][rbx-1]
    S += m[lty-1][ltx-1]
    return S

ans = 0
for y in range(1,K+2):
    for x in range(1,K+2):
        ltw = cs2(wcumsum,x,y,x+K, y+K)
        rbw = cs2(wcumsum,x+K,y+K,x+2*K, y+2*K)
        lbh = cs2(hcumsum,x,y+K,x+K, y+2*K)
        rth = cs2(hcumsum,x+K,y,x+2*K, y+K)
        temp = ltw + rbw + lbh + rth
        ans = max(ans,temp)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import numpy as np

n,k = list(map(int, input().split()))
v0 = np.zeros((4*k, 4*k), dtype=int)
v1 = np.zeros((4*k, 4*k), dtype=int)

for i in range(n):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    x %= 2*k
    y %= 2*k
    if c=="W":
        v = v0
    else:
        v = v1
    v[x][y] += 1
    v[x][y+2*k] += 1
    v[x+2*k][y] += 1
    v[x+2*k][y+2*k] += 1
def cumsum2(v):
    # v: h*wの2次元リスト
    v = np.cumsum(v, axis=0)
    v = np.cumsum(v, axis=1)
    c = np.zeros((v.shape[0]+1, v.shape[1]+1), dtype=int)
    c[1:, 1:] = v
    return v
c0 = cumsum2(v0)
c1 = cumsum2(v1)
ans = -1
i0 = []
i1 = []
for i in range(2*k):
    for j in range(2*k-i):
        i0.append([[i+k,j+k], [i+k,j], [i,j+k], [i,j], [i+2*k, j+2*k], [i+2*k,j+k], [i+k, j+2*k], [i+k, j+k]])
        i1.append([[i+2*k, j+k], [i+2*k,j], [i+k,j+k], [i+k,j], [i+k, j+2*k], [i+k,j+k], [i,j+2*k], [i,j+k]])
#         val0 = c0[i+k][j+k]-c0[i+k][j]-c0[i][j+k]+c0[i][j] + c0[i+2*k][j+2*k]-c0[i+2*k][j+k]-c0[i+k][j+2*k]+c0[i+k][j+k]
#         val1 = c1[i+2*k][j+k]-c1[i+2*k][j]-c1[i+k][j+k]+c1[i+k][j] + c1[i+k][j+2*k]-c1[i+k][j+k]-c1[i][j+2*k]+c1[i][j+k]
#         ans = max(ans, val0+val1)
i0 = np.array(i0)
i1 = np.array(i1)
val = c0[i0[:,[0,3,4,7],0], i0[:,[0,3,4,7],1]].sum(axis=1) - c0[i0[:,[1,2,5,6],0], i0[:,[1,2,5,6],1]].sum(axis=1) + c1[i1[:,[0,3,4,7],0], i1[:,[0,3,4,7],1]].sum(axis=1) - c1[i1[:,[1,2,5,6],0], i1[:,[1,2,5,6],1]].sum(axis=1)
print(val.max())

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n,k = list(map(int, input().split()))
v0 = [[0]*(2*k) for _ in range(2*k)]
v1 = [[0]*(2*k) for _ in range(2*k)]

for i in range(n):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    x %= 2*k
    y %= 2*k
    if c=="W":
        v = v0
    else:
        v = v1
    v[x][y] += 1
#     v[x][y+2*k] += 1
#     v[x+2*k][y] += 1
#     v[x+2*k][y+2*k] += 1
def cumsum2(v):
    # v: h*wの2次元リスト
    h,w = len(v), len(v[0])
    v.insert(0, [0]*w)
    for l in v:
        l.insert(0, 0)
    for i in range(1,h+1):
        for j in range(1,w+1):
            v[i][j] = v[i-1][j] + v[i][j-1] - v[i-1][j-1] + v[i][j]
    return v
c0 = cumsum2(v0)
c1 = cumsum2(v1)
ans = -1
def sub(c, i, j):
    i %= 2*k
    j %= 2*k
    l = []
    if i<k and j<k:
        l = [[i,j,i+k,j+k]]
    elif i>=k and j<k:
        l = [[i,2*k,j,j+k], [0,i-k,j,j+k]]
    elif i<k and j>=k:
        l = [[i,i+k,j,2*k], [i,i+k,0,j-k]]
    else:
        l = [[i,2*k,j,2*k], [0,i-k,j,2*k], [i,2*k,0,j-k], [0,i-k,0,j-k]]
#     print(i,j,l)
    return sum((c[z][w] - c[z][y] - c[x][w] + c[x][y]) for x,z,y,w in l)
for i in range(2*k):
    for j in range(2*k-i):
        val0 = sub(c0, i, j) + sub(c0, i+k, j+k)
        val1 = sub(c1, i+k, j) + sub(c1, i, j+k)
        ans = max(ans, val0+val1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n,k = list(map(int, input().split()))
v0 = [[0]*(2*k) for _ in range(2*k)]
v1 = [[0]*(2*k) for _ in range(2*k)]

for i in range(n):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    x %= 2*k
    y %= 2*k
    if c=="W":
        v = v0
    else:
        v = v1
    v[x][y] += 1
#     v[x][y+2*k] += 1
#     v[x+2*k][y] += 1
#     v[x+2*k][y+2*k] += 1
def cumsum2(v):
    # v: h*wの2次元リスト
    h,w = len(v), len(v[0])
    v.insert(0, [0]*w)
    for l in v:
        l.insert(0, 0)
    for i in range(1,h+1):
        for j in range(1,w+1):
            v[i][j] = v[i-1][j] + v[i][j-1] - v[i-1][j-1] + v[i][j]
    return v
c0 = cumsum2(v0)
c1 = cumsum2(v1)
ans = -1
def sub(c, i, j):
    i %= 2*k
    j %= 2*k
    l = []
    if i<=k and j<=k:
        l = [[i,j,i+k,j+k]]
    elif i>k and j<=k:
        l = [[i,2*k,j,j+k], [0,i-k,j,j+k]]
    elif i<=k and j>k:
        l = [[i,i+k,j,2*k], [i,i+k,0,j-k]]
    else:
        l = [[i,2*k,j,2*k], [0,i-k,j,2*k], [i,2*k,0,j-k], [0,i-k,0,j-k]]
    return sum((c[z][w] - c[z][y] - c[x][w] + c[x][y]) for x,z,y,w in l)
for i in range(2*k):
    for j in range(2*k):
        val0 = sub(c0, i, j) + sub(c0, i+k, j+k)
        val1 = sub(c1, i+k, j) + sub(c1, i, j+k)
        ans = max(ans, val0+val1)
print(ans)

Submission status: Wrong Answer

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

A = [[ 0 for _ in range(K2) ] for _ in range(K2)]
for _ in range(N):
  x,y,c = input().split()
  x,y = int(x) % (K2), int(y) % (K2)
  if c == 'W':
    y = (y+K) % (K2)
  #if y >= K:
  #  x,y = (x+K) %K2, y-K
  A[x][y] += 1

for i in range(K2):
  A[i] = A[i]  + A[i][:K-1]
  
for i in range(K-1):
  A.append(A[i])
  
#for a in A:
#  print(a)


B = [[ 0 for _ in range(K2+K) ] for _ in range(K2+K)]
for i in range(K2+K-1):
  for j in range(K2+K-1):
    B[i+1][j+1] = B[i+1][j] + B[i][j+1] - B[i][j] + A[i][j]
    
ans = 0
for i in range(K):
  for j in range(K):
    # (i,j)(i+K-1)(j+K-1) , (i+K,j+K), (i+2k-1)(j+2k-1)
    wk = 0
    wk += B[i+K][j+K] - B[i][j+K] - B[i+K][j] + B[i][j]
    wk += B[i+K*2][j+K*2] - B[i+K][j+K*2] - B[i+K*2][j+K] + B[i+K][j+K]
    ans = max(wk,ans)
#for b in B:
#  print(b)
  
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


def main():
    n, k = map(int, input().split())
    hopes = [[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 == "B":
            x += k
        x %= 2*k
        y %= 2*k
        hopes[y+1][x+1] += 1

    hopes = np.array(hopes)
    cumsum = np.cumsum(np.cumsum(hopes, axis=0), axis=1)

    last = np.full(k+1, fill_value=2*k)
    y_starts = np.arange(1, k+2)
    shift_y = y_starts + k - 1

    ans = 0
    for i in range(1, k+1):
        x_starts = np.full(k+1, i)
        shift_x = x_starts + k - 1

        top_left = cumsum[last, x_starts-1] - cumsum[shift_y, x_starts-1]
        top_right = cumsum[last, last] - cumsum[last, shift_x] - cumsum[shift_y, last] + cumsum[shift_y, shift_x]
        center = cumsum[shift_y, shift_x] - cumsum[shift_y, x_starts-1] - cumsum[y_starts-1, shift_x] + cumsum[y_starts-1, x_starts-1]
        low_left = cumsum[y_starts-1, x_starts-1]
        low_right = cumsum[y_starts-1, last] - cumsum[y_starts-1, shift_x]

        result = (top_left + top_right + center + low_left + low_right).max()
        if result > ans:
            ans = result

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


def main():
    n, k = map(int, input().split())
    hopes = [[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 == "B":
            x += k
        x %= 2*k
        y %= 2*k
        hopes[y+1][x+1] += 1

    hopes = np.array(hopes)
    cumsum = np.cumsum(np.cumsum(hopes, axis=0), axis=1)

    last = np.full(k+1, fill_value=2*k)
    y_starts = np.arange(k+1)
    shift_y = y_starts + k

    ans = 0
    for i in range(k+1):
        x_starts = np.full(k+1, i)
        shift_x = x_starts + k

        top_left = cumsum[last, x_starts] - cumsum[shift_y, x_starts]
        top_right = cumsum[last, last] - cumsum[last, shift_x] - cumsum[shift_y, last] + cumsum[shift_y, shift_x]
        center = cumsum[shift_y, shift_x] - cumsum[shift_y, x_starts] - cumsum[y_starts, shift_x] + cumsum[y_starts, x_starts]
        low_left = cumsum[y_starts, x_starts]
        low_right = cumsum[y_starts, last] - cumsum[y_starts, shift_x]

        result = (top_left + top_right + center + low_left + low_right).max()
        if result > ans:
            ans = result

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


def main():
    n, k = map(int, input().split())
    hopes = [[0] * (2*k) for _ in range(2*k)]
    for _ in range(n):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == "B":
            x += k
        x %= 2*k
        y %= 2*k
        hopes[y][x] += 1

    hopes = np.array(hopes)
    hopes = np.vstack((hopes, hopes))
    hopes = np.hstack((hopes, hopes))
    cumsum = np.cumsum(np.cumsum(hopes, axis=0), axis=1)
    y_starts = np.arange(2*k)
    y_ends = y_starts + k
    ans = 0
    for i in range(2*k):
        x_starts = np.full(2*k, fill_value=i, dtype=np.int16)
        x_ends = x_starts + k
        results = cumsum[x_ends, y_ends]\
                  - cumsum[x_starts, y_ends]\
                  - cumsum[x_ends, y_starts]\
                  + cumsum[x_starts, y_starts]

        candidate = results.max()
        if candidate > ans:
            ans = candidate

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

read=sys.stdin.read
readline=sys.stdin.readline

def main():
  wb={'W':0,'B':1}
  n,k=map(int,readline().split())
  xyc=[l.split() for l in read().splitlines()]
  xy=[[int(lst[0]) % (2*k),(int(lst[1])+k*wb[lst[2]]) % (2*k)] for lst in xyc]
  mat=np.zeros((k+1,2*k+1),dtype='int32')
  cand=np.zeros((k+1,k+1),dtype='int32')
  for e in xy:
    f0=e[0]>=k
    f1=e[1]>=k
    mat[e[0]-f0*k+1,e[1]+(-1)**f1*f0*k+1]+=1
  mat=np.cumsum(mat,axis=0)
  mat=np.cumsum(mat,axis=1)
  cand=mat[k,2*k]-mat[k,k:2*k+1]+mat[k,:k+1]\
       -np.reshape(mat[:k+1,2*k],(k+1,1))+2*mat[:,k:2*k+1]-2*mat[:,:k+1]
  print(np.max(cand))
  
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

read=sys.stdin.read
readline=sys.stdin.readline

def main():
  wb={'W':0,'B':1}
  n,k=map(int,readline().split())
  xyc=[l.split() for l in read().splitlines()]
  xy=[[int(lst[0]) % (2*k),(int(lst[1])+k*wb[lst[2]]) % (2*k)] for lst in xyc]
  mat=np.zeros((k+1,2*k+1),dtype='int64')
  cand=np.zeros((k+1,k+1),dtype='int64')
  for e in xy:
    f0=e[0]>=k
    f1=e[1]>=k
    mat[e[0]-f0*k+1,e[1]+(-1)**f1*f0*k+1]+=1
  mat=np.cumsum(mat,axis=0)
  mat=np.cumsum(mat,axis=1)
  cand=mat[k,2*k]-mat[k,k:2*k+1]+mat[k,:k+1]\
       -np.reshape(mat[:k+1,2*k],(k+1,1))+2*mat[:,k:2*k+1]-2*mat[:,:k+1]
  print(np.max(cand))
  
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

read=sys.stdin.read
readline=sys.stdin.readline

def main():
  wb={'W':0,'B':1}
  n,k=map(int,readline().split())
  xyc=[l.split() for l in read().splitlines()]
  xy=[[int(lst[0]) % (2*k),(int(lst[1])+k*3*wb[lst[2]]) % (2*k)] for lst in xyc]
  mat=np.zeros((k+1,2*k+1),dtype='int64')
  cand=np.zeros((k+1,k+1),dtype='int64')
  for e in xy:
    f0=e[0]>=k
    f1=e[1]>=k
    mat[e[0]-f0*k+1,e[1]+(-1)**f1*f0*k+1]+=1
  mat=np.cumsum(mat,axis=0)
  mat=np.cumsum(mat,axis=1)
  cand=mat[k,2*k]-mat[k,k:2*k+1]+mat[k,:k+1]\
       -np.reshape(mat[:k+1,2*k],(k+1,1))+2*mat[:,k:2*k+1]-2*mat[:,:k+1]
  print(np.max(cand))
  
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

read=sys.stdin.read
readline=sys.stdin.readline

def main():
  wb={'W':0,'B':1}
  n,k=map(int,readline().split())
  xyc=[l.split() for l in read().splitlines()]
  xy=[[int(lst[0]) % (2*k),(int(lst[1])-k*wb[lst[2]]) % (2*k)] for lst in xyc]
  mat=np.zeros((k+1,2*k+1),dtype='int64')
  cand=np.zeros((k+1,k+1),dtype='int64')
  for e in xy:
    f0=e[0]>=k
    f1=e[1]>=k
    mat[e[0]-f0*k+1,e[1]+(-1)**f1*f0*k+1]+=1
  mat=np.cumsum(mat,axis=0)
  mat=np.cumsum(mat,axis=1)
  cand=mat[k,2*k]-mat[k,k:2*k+1]+mat[k,:k+1]\
       -np.reshape(mat[:k+1,2*k],(k+1,1))+2*mat[:,k:2*k+1]-2*mat[:,:k+1]
  print(np.max(cand))
  
if __name__=='__main__':
  main()