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:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
ps = []
imos = [[0] * (2 * K) for _ in range(2 * K)]
def checker():
  for im in imos: print(*im)
  print()
bs = 0
for i in range(N):
  u, v, t = input().split()
  u = int(u)
  v = int(v)
  ps.append((u, v, t))
  if t == "B":
    bs += 1
    imos[(u + K + 1) % (2 * K)][(v + K + 1) % (2 * K)] += 1
    imos[(u + 1) % (2 * K)][(v + K + 1) % (2 * K)] -= 1
    imos[(u + K + 1) % (2 * K)][(v + 1) % (2 * K)] -= 1
    imos[(u + 1) % (2 * K)][(v + 1) % (2 * K)] += 1
  else:
    imos[(u + K + 1) % (2 * K)][(v + K + 1) % (2 * K)] += -1
    imos[(u + 1) % (2 * K)][(v + K + 1) % (2 * K)] -= -1
    imos[(u + K + 1) % (2 * K)][(v + 1) % (2 * K)] -= -1
    imos[(u + 1) % (2 * K)][(v + 1) % (2 * K)] += -1


#checker()
for i in range(2 * K):
  for j in range(2 * K):
    imos[i][(j + 1) % (2 * K)] += imos[i][j]
for i in range(2 * K):
  for j in range(2 * K):
    imos[(i + 1) % (2 * K)][j] += imos[i][j]
checker()
print(bs)
res = 0
for i in range(2 * K):
  for j in range(2 * K):
    res = max(res, imos[i][j])
print(res + bs)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    
    imos2d = [[0]*(2*K+1) for _ in range(2*K+1)]
    
    def get_cord(x):
        if x<K-1:
            return [(0,x+1), (x+K+1,2*K)]
        else:
            return [(x-K+1,x+1)]

    for _ in range(N):
        x,y,c = ST().split()
        x,y = int(x), int(y)
        if c=="W":
            x+=K
        x,y = x%(2*K), y%(2*K)
        for base in [0,K]:
            for l,r in get_cord((x+base)%(2*K)):
                for u,d in get_cord((y+base)%(2*K)):
                    imos2d[l][u] += 1
                    imos2d[l][d] -= 1
                    imos2d[r][u] -= 1
                    imos2d[r][d] -= 1

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

    ans = 0
    for a in imos2d:
        ans = max(ans,max(a))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class cumSum2D():
    mazeSum = []
    h, w = 0, 0

    def __init__(self):
        self.mazeSum = []

    def load(self, maze):
        self.h, self.w = len(maze), len(maze[0])
        # 2次元累積和は端の計算が面倒なので、0の行と0の列は0でうめ、1,1からうめていく
        for _ in range(self.h + 1):
            self.mazeSum.append([0] * (self.w + 1))
        for y in range(self.h):
            for x in range(self.w):
                res = maze[y][x]
                res += self.mazeSum[y + 1][x]
                res += self.mazeSum[y][x + 1]
                res -= self.mazeSum[y][x]
                self.mazeSum[y + 1][x + 1] = res

    def query(self, x0, y0, x1, y1):
        """
        [x0, [y0 からx1), y1)の2次元累積和
        x0,y0は閉区間, x1,y1は開区間です
        """
        # 0のほうが原点に近くあってほしい
        if x0 > x1 or y0 > y1:
            raise ValueError
        res = self.mazeSum[y1][x1]
        res -= self.mazeSum[y1][x0]
        res -= self.mazeSum[y0][x1]
        res += self.mazeSum[y0][x0]
        return res

n, k = map(int, input().split())
dat = []
mapW, mapB = [], []
# Wでhitするmap と Bでhitするmap
for _ in range(k):
    mapW.append([0] * k)
    mapB.append([0] * k)

# 圧縮を行う
for i in range(n):
    inp = input().split()
    # colorの列はW,B -> 0,1に変えておく
    x, y, c = int(inp[0]), int(inp[1]), 0 if inp[2] == "W" else 1
    x = x % (2*k)
    y = y % (2*k)
    # 第一象限か第三象限にいる場合はそのまま[0,k)の区間に詰め込む
    if (0 <= x < k and 0 <= y < k) or (k <= x  and k <= y):
        dat.append( (x % k, y % k, c) )
        if c == 0:
            mapW[y%k][x%k] += 1
        else:
            mapB[y%k][x%k] += 1


    # 第二象限か第四象限の場合は判定する色を反転させて[0,k)の区間に詰め込む
    else:
        dat.append( (x % k, y % k, 0 if c == 1 else 1 ))
        if c == 1:
            mapW[y%k][x%k] += 1
        else:
            mapB[y%k][x%k] += 1

csw, csb = cumSum2D(), cumSum2D()
csw.load(mapW)
csb.load(mapB)

fres = -1
for yy in range(k+1):
    for xx in range(k+1):
        a = csw.query(0, 0, xx, yy)
        d = csw.query(xx, yy, k, k)
        b = csb.query(xx, 0, k, yy)
        c = csb.query(0, yy, xx, k)
        res = a+b+c+d
        fres = max(fres, res)
print(fres)

Submission status: Wrong Answer

Solution code:
"""
maze[h][w]2次元累積和を作成し、
[x0, [y0, (x1), y1)の区間のクエリ
★x0,y0は閉区間, x1,y1は開区間です
load: O(h*w)
query: O(1)
update: 未サポート
"""
class cumSum2D():
    mazeSum = []
    h, w = 0, 0

    def __init__(self):
        self.mazeSum = []

    def load(self, maze):
        self.h, self.w = len(maze), len(maze[0])
        # 2次元累積和は端の計算が面倒なので、0の行と0の列は0でうめ、1,1からうめていく
        for _ in range(self.h + 1):
            self.mazeSum.append([0] * (self.w + 1))
        for y in range(self.h):
            for x in range(self.w):
                res = maze[y][x]
                res += self.mazeSum[y + 1][x]
                res += self.mazeSum[y][x + 1]
                res -= self.mazeSum[y][x]
                self.mazeSum[y + 1][x + 1] = res

    def query(self, x0, y0, x1, y1):
        """
        [x0, [y0 からx1), y1)の2次元累積和
        x0,y0は閉区間, x1,y1は開区間です
        """
        # 0のほうが原点に近くあってほしい
        if x0 > x1 or y0 > y1:
            raise ValueError
        res = self.mazeSum[y1][x1]
        res -= self.mazeSum[y1][x0]
        res -= self.mazeSum[y0][x1]
        res += self.mazeSum[y0][x0]
        return res

n, k = map(int, input().split())
dat = []

mapW, mapB = [], []
# Wでhitするmap と Bでhitするmap
for _ in range(k):
    mapW.append([0] * k)
    mapB.append([0] * k)

# 圧縮を行う
for i in range(n):
    inp = input().split()
    # colorの列はW,B -> 0,1に変えておく
    x, y, c = int(inp[0]), int(inp[1]), 0 if inp[2] == "W" else 1
    x = x % (2*k)
    y = y % (2*k)
    # 第一象限か第三象限にいる場合はそのまま[0,k)の区間に詰め込む
    if (0 <= x < k and 0 <= y < k) or k <= x  and k <= y:
        dat.append( (x % k, y % k, c) )
        if c == 0:
            mapW[y%k][x%k] += 1
        else:
            mapB[y%k][x%k] += 1


    # 第二象限か第四象限の場合は判定する色を反転させて[0,k)の区間に詰め込む
    else:
        dat.append( (x % k, y % k, 0 if c == 1 else 1 ))
        if c == 1:
            mapW[y%k][x%k] += 1
        else:
            mapB[y%k][x%k] += 1

csw, csb = cumSum2D(), cumSum2D()
csw.load(mapW)
csb.load(mapB)
from pprint import pprint
"""
pprint(mapW)
pprint(mapB)
pprint(csw.h)
pprint(csw.w)
pprint(csw.mazeSum)
pprint(csb.mazeSum)
"""

fres = -1

for yy in range(k + 1):
    for xx in range(k + 1):
        res = 0
        a = csw.query(0, 0, xx, yy)
        d = csw.query(xx, yy, k, k)
        b = csb.query(xx, 0, k, yy)
        c = csb.query(0, yy, xx, k)
        res = a+b+c+d

        fres = max(fres, res)
print(fres)

Submission status: Wrong Answer

Solution code:
class cumSum2D():
    mazeSum = []
    h, w = 0, 0

    def __init__(self):
        self.mazeSum = []

    def load(self, maze):
        self.h, self.w = len(maze), len(maze[0])
        # 2次元累積和は端の計算が面倒なので、0の行と0の列は0でうめ、1,1からうめていく
        for _ in range(self.h + 1):
            self.mazeSum.append([0] * (self.w + 1))
        for y in range(self.h):
            for x in range(self.w):
                res = maze[y][x]
                res += self.mazeSum[y + 1][x]
                res += self.mazeSum[y][x + 1]
                res -= self.mazeSum[y][x]
                self.mazeSum[y + 1][x + 1] = res

    def query(self, x0, y0, x1, y1):
        """
        [x0, [y0 からx1), y1)の2次元累積和
        x0,y0は閉区間, x1,y1は開区間です
        """
        # 0のほうが原点に近くあってほしい
        if x0 > x1 or y0 > y1:
            raise ValueError
        res = self.mazeSum[y1][x1]
        res -= self.mazeSum[y1][x0]
        res -= self.mazeSum[y0][x1]
        res += self.mazeSum[y0][x0]
        return res

n, k = map(int, input().split())
dat = []

mapW, mapB = [], []
# Wでhitするmap と Bでhitするmap
for _ in range(k):
    mapW.append([0] * k)
    mapB.append([0] * k)

# 圧縮を行う
for i in range(n):
    inp = input().split()
    # colorの列はW,B -> 0,1に変えておく
    x, y, c = int(inp[0]), int(inp[1]), 0 if inp[2] == "W" else 1
    x = x % (2*k)
    y = y % (2*k)
    # 第一象限か第三象限にいる場合はそのまま[0,k)の区間に詰め込む
    if (0 <= x < k and 0 <= y < k) or k <= x  and k <= y:
        dat.append( (x % k, y % k, c) )
        if c == 0:
            mapW[y%k][x%k] += 1
        else:
            mapB[y%k][x%k] += 1


    # 第二象限か第四象限の場合は判定する色を反転させて[0,k)の区間に詰め込む
    else:
        dat.append( (x % k, y % k, 0 if c == 1 else 1 ))
        if c == 1:
            mapW[y%k][x%k] += 1
        else:
            mapB[y%k][x%k] += 1

csw, csb = cumSum2D(), cumSum2D()
csw.load(mapW)
csb.load(mapB)
from pprint import pprint
"""
pprint(mapW)
pprint(mapB)
pprint(csw.h)
pprint(csw.w)
pprint(csw.mazeSum)
pprint(csb.mazeSum)
"""

fres = -1

for yy in range(k):
    for xx in range(k):
        res = 0
        a = csw.query(0, 0, xx, yy)
        d = csw.query(xx, yy, k, k)
        b = csb.query(xx, 0, k, yy)
        c = csb.query(0, yy, xx, k)
        res = a+b+c+d

        fres = max(fres, res)
print(fres)

Submission status: Wrong Answer

Solution code:
import copy
from datetime import datetime

#print(datetime.now())
n,k = map(int ,input().split())
p = [[0] * (2*k) for i in range(2*k)]
ans = 0
for i in range(n):
  x,y,c = input().split()
  x = int(x)
  y = int(y)
  if c == 'B':
    x += k
  p[x%(2*k)][y%(2*k)] += 1
#[print(p[i]) for i in range(2*k)]
#print()
#print(datetime.now())

csum1 = copy.deepcopy(p)
for i in range(2*k):
    for j in range(1, k):
        csum1[i][0] += p[i][j]
    for j in range(1, 2*k):
        csum1[i][j] = csum1[i][j-1] - p[i][j-1] + p[i][(j+k-1)%(2*k)]
#print(datetime.now())
#[print(csum1[i]) for i in range(2*k)]
#print()

csum2 = copy.deepcopy(csum1)
#print(datetime.now())
for j in range(2*k):
    for i in range(1, k):
        csum2[0][j] += csum1[i][j]
    for i in range(1, 2*k):
        csum2[i][j] = csum2[i-1][j] - csum1[i-1][j] + csum1[(i+k-1)%(2*k)][j]

#[print(csum2[i]) for i in range(2*k)]
#print(datetime.now())
for i in range(k):
    for j in range(k):
        ans = max(ans, csum2[i][j] + csum2[i+k][j+k])

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
dat = []

mapW, mapB = [], []
# Wでhitするmap と Bでhitするmap
for _ in range(k):
    mapW.append([0] * k)
    mapB.append([0] * k)

# 圧縮を行う
for i in range(n):
    inp = input().split()
    # colorの列はW,B -> 0,1に変えておく
    x, y, c = int(inp[0]), int(inp[1]), 0 if inp[2] == "W" else 1
    x = x % (k * 2)
    y = y % (k * 2)
    # 第一象限か第三象限にいる場合はそのまま[0,k)の区間に詰め込む
    if (0 <= x < k and 0 <= y < k) or k <= x  and k <= y:
        dat.append( (x % k, y % k, c) )

    # 第二象限か第四象限の場合は判定する色を反転させて[0,k)の区間に詰め込む
    else:
        dat.append( (x % k, y % k, 0 if c == 1 else 1 ))

fres = -1

for i in range(k):
    for ii in range(k):
        res = 0
        for j in range(n):
            x, y, c = dat[j]
            #print("is x={0} y={1} i={2} ii = {3}".format(x, y, i, ii))
            if i <= x and ii <= y:
                if c == 0:
                    #print("white1")
                    res += 1
                    continue
            elif i <= x and  ii > y:
                if c == 1:
                    #print("black")
                    res += 1
                    continue
            elif i >  x and ii <= y:
                if c == 1:
                    #print("black")
                    res += 1
                    continue
            else:
                if c == 0:
                    #print("white1")
                    res += 1
                    continue
        fres = max(fres, res)
print(fres)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
dat = []
xxx = 2 * k
for i in range(n):
    inp = input().split()
    x, y, c = int(inp[0]), int(inp[1]), 0 if inp[2] == "W" else 1
    if 0 <= x < k and 0 <= y < k:
        dat.append( (x % k, y % k, c) )
    elif k <= x  and k <= y:
        dat.append((x % k, y % k, c))
    else:
        dat.append((x % k, y % k, 0 if c == 1 else 1 ))
#print(dat)
fres = -1

for i in range(k + 1):
    for ii in range(k + 1):
        res = 0
        for j in range(n):
            x, y, c = dat[j]
            #print("is x={0} y={1} i={2} ii = {3}".format(x, y, i, ii))
            if i <= x and ii <= y:
                if c == 0:
                    #print("white1")
                    res += 1
                    continue
            elif i <= x and  ii > y:
                if c == 1:
                    #print("black")
                    res += 1
                    continue
            elif i >  x and ii <= y:
                if c == 1:
                    #print("black")
                    res += 1
                    continue
            else:
                if c == 0:
                    #print("white1")
                    res += 1
                    continue
        fres = max(fres, res)
print(fres)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
dat = []
xxx = 2 * k
for i in range(n):
    inp = input().split()
    x, y, c = int(inp[0]), int(inp[1]), 0 if inp[2] == "W" else 1
    if 0 <= x < k and 0 <= y < k:
        dat.append( (x % k, y % k, c) )
    elif k <= x  and k <= y:
        dat.append((x % k, y % k, c))
    else:
        dat.append((x % k, y % k, 0 if c == 1 else 1 ))
#print(dat)
fres = -1

for i in range(k):
    for ii in range(k):
        res = 0
        for j in range(n):
            x, y, c = dat[j]
            #print("is x={0} y={1} i={2} ii = {3}".format(x, y, i, ii))
            if i <= x and ii <= y:
                if c == 0:
                    #print("white1")
                    res += 1
                    continue
            elif i <=x and  ii > y:
                if c == 1:
                    #print("black")
                    res += 1
                    continue
            elif i >  x and ii <= y:
                if c == 1:
                    #print("black")
                    res += 1
                    continue
            else:
                if c == 0:
                    #print("white1")
                    res += 1
                    continue
        fres = max(fres, res)
print(fres)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
g=[[]*3 for i in range(n)]
for i in range(n):
  g[i]=list(input().split())
for i in range(n):
  if g[i][2]=="W":
    g[i][0]=int((int(g[i][0])+k)%(2*k))
    g[i][1]=int((int(g[i][1]))%(2*k))
  else:
    g[i][0]=int((int(g[i][0]))%(2*k))
    g[i][1]=int((int(g[i][1]))%(2*k))
A=[[0]*(2*k) for i in range(2*k)]
for i in range(n):
  A[g[i][0]][g[i][1]]+=1
ans=0
for i in range(2*k):
  for j in range(2*k):
    a=0
    for k in range(k):
      for l in range(k):
        a=a+A[(i+k)%(2*k)][(j+l)%(2*k)]
    if a>ans:
      ans=a
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

X = []
Y = []

for k in range(N):
  x, y, c = input().split()
  x = int(x) % (2*K)
  y = int(y)
  if c == 'W':
    y += K
  y = y % (2*K)
  
  X.append(x)
  Y.append(y)

ans = 0
for i in range(-K+1,K):
  for j in range(-K+1,K):
    tmp_ans = 0
    
    for k in range(N):
      tmp_x = X[k]
      tmp_y = Y[k]
      
      if i <= tmp_x and i+K > tmp_x:
        if j <= tmp_y and j+K > tmp_y:
          tmp_ans += 1
      elif i > tmp_x and j > tmp_y:
        tmp_ans += 1
      elif i > tmp_x and j + K <= tmp_y:
        tmp_ans += 1
      elif i + K <= tmp_x and j > tmp_y:
        tmp_ans += 1
      elif i + K <= tmp_x and j + K <= tmp_y:
        tmp_ans += 1
    
    if ans < tmp_ans:
      ans = tmp_ans

print(ans)

Submission status: Wrong Answer

Solution code:
class Acc2D:
    def __init__(self, a):
        h, w = len(a), len(a[0])
        self.acc2D = self._build(h, w, a)

    def _build(self, h, w, a):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r][c + 1] + ret[r + 1][c] - ret[r][c] + a[r][c]
                # 末項は必要に応じて改変すること
        return ret

    def get(self, r1, r2, c1, c2):
        # [r1,r2), [c1,c2) : 0-indexed
        acc2D = self.acc2D
        return acc2D[r2][c2] - acc2D[r1][c2] - acc2D[r2][c1] + acc2D[r1][c1]


def main():
    import sys

    input = sys.stdin.readline

    n, k = map(int, input().split())

    g = [[0] * (k * 2) for _ in range(k * 2)]
    for _ in range(n):
        x, y, c_ = input().split()
        x = int(x) % (k * 2)
        y = int(y) % (k * 2)
        if c_ == 'W':
            y = (y + k) % (k * 2)
            # すべて黒にする
        g[y][x] = 1

    acc2D = Acc2D(g)

    ret = 0
    # 中央にk*kの区画をとり、黒または白に塗る(条件を満たす個数:黒=s,白=n-s)
    # 4辺を伸ばして、2k*2kの区画を分割し、各区画を評価する
    for r in range(k):  # r+k < k*2
        for c in range(k):  # c+k < k*2
            s = (
                    acc2D.get(0, r, 0, c)
                    + acc2D.get(0, r, c + k, k * 2)
                    + acc2D.get(r, r + k, c, c + k)
                    + acc2D.get(r + k, k * 2, 0, c)
                    + acc2D.get(r + k, k * 2, c + k, k * 2)
            )
            ret = max(ret, s, n - s)

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

M = np.zeros((K2, K2), int)
nb = 0
for _ in range(N):
  x, y, c = input().split()
  x = int(x) % K2
  y = int(y) % K2
  if c=='B': nb+=1
  M[x, y] += 1 if c=='W' else -1

Sx = np.zeros((K2, K2+1), int)
for y in range(K2):
  Sx[:, y+1] = Sx[:, y] + M[:, y]

S = np.zeros((K2+1, K2+1), int)
for x in range(K2):
  S[x+1] = S[x] + Sx[x]

for x in range(K2):
  x0 = 0
  x1 = max(x-K , 0)
  x2 = x
  x3 = min(x+K , K2)
  x4 = K2

  T1 = S[x4] - S[x3] + S[x2] - S[x1]
  T2 = S[x3] - S[x2] + S[x1] - S[x0]

  U = T1[K2] - T1[K:K2] + T1[:K] + T2[K:K2] - T2[:K]
  
print(nb + np.max(U))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
K2 = K*2
M = [[0]*K2 for _ in range(K2)]
nb = 0
for _ in range(N):
  x, y, c = input().split()
  x = int(x)
  y = int(y)
  if c=='B': nb+=1
  M[x%K2][y%K2] += 1 if c=='W' else -1

Sx = [[0]*(K2+1) for _ in range(K2)]
for x, (s, m) in enumerate(zip(Sx, M)):
  #for y in range(K2):
  #  s[y+1] = s[y] + m[y]
  for y, my in enumerate(m):
    s[y+1] = s[y] + my
    
S = [[0]*(K2+1) for _ in range(K2+1)]
for x in range(K2):
  for y in range(1,K2+1):
    S[x+1][y] = S[x][y] + Sx[x][y]
    
def sc(x1, y1):
  x0 = max(x1-K, 0)
  y0 = max(y1-K, 0)
  x1 = min(x1, K2)
  y1 = min(y1, K2)
  return S[x1][y1] - S[x0][y1] - S[x1][y0] + S[x0][y0]

ans = -1000000
for x in range(K+1):
  for y in range(K+1):
    score = sc(x,y) + sc(x+K, y+K) + sc(x+K2, y+K2) + sc(x+K2, y) + sc(x, y+K2)
    ans = max(ans, score)

print(nb+ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
K2 = K*2
M = [[0]*K2 for _ in range(K2)]
nb = 0
for _ in range(N):
  x, y, c = input().split()
  x = int(x)
  y = int(y)
  if c=='B': nb+=1
  M[x%K2][y%K2] += 1 if c=='W' else -1

Sx = [[0]*(K2+1) for _ in range(K2)]
for x, (s, m) in enumerate(zip(Sx, M)):
  #for y in range(K2):
  #  s[y+1] = s[y] + m[y]
  for y, my in enumerate(m):
    s[y+1] = s[y] + my
    
S = [[0]*(K2+1) for _ in range(K2+1)]
for x in range(K2):
  for y in range(1,K2+1):
    S[x+1][y] = S[x][y] + Sx[x][y]
    
def sc(x1, y1):
  x0 = max(x1-K, 0)
  y0 = max(y1-K, 0)
  x1 = min(x1, K2)
  y1 = min(y1, K2)
  return S[x1][y1] - S[x0][y1] - S[x1][y0] + S[x0][y0]

ans = 0
for x in range(K+1):
  for y in range(K+1):
    score = sc(x,y) + sc(x+K, y+K) + sc(x+K2, y+K2) + sc(x+K2, y) + sc(x, y+K2)
    ans = max(ans, score)

print(nb+ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
K2 = K*2
M = [[0]*K2 for _ in range(K2)]
nb = 0
for _ in range(N):
  x, y, c = input().split()
  x = int(x)
  y = int(y)
  if c=='B': nb+=1
  M[x%K2][y%K2] += 1 if c=='W' else -1

Sx = [[0]*(K2+1) for _ in range(K2)]
for x, (s, m) in enumerate(zip(Sx, M)):
  #for y in range(K2):
  #  s[y+1] = s[y] + m[y]
  for y, my in enumerate(m):
    s[y+1] = s[y] + my
    
S = [[0]*(K2+1) for _ in range(K2+1)]
for x in range(K2):
  for y in range(1,K2+1):
    S[x+1][y] = S[x][y] + Sx[x][y]
    
def sc(x1, y1):
  x0 = max(x1-K, 0)
  y0 = max(y1-K, 0)
  x1 = min(x1, K2)
  y1 = min(y1, K2)
  return S[x1][y1] - S[x0][y1] - S[x1][y0] + S[x0][y0]

ans = 0
for x in range(K):
  for y in range(K):
    score = sc(x,y) + sc(x+K, y+K) + sc(x+K2, y+K2) + sc(x+K2, y) + sc(x, y+K2)
    ans = max(ans, score)

print(nb+ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
li = [list(map(str,input().split())) for i in range(n)]
for i in li:
  i[0] = int(i[0])
  i[1] = int(i[1])
  if i[2]=="B":
    i[1] += k
    i[2] = "W"
  i[0] %= (2*k)
  i[1] %= (2*k)
#実現できる希望の数を全探索してmaxをとる
realizable = [] #実現できる希望の数のリスト
for i in range(k):
  for j in range(k):
    c=[r for r in li if (r[0]-i)//k==0 and (r[1]-j)//k==0]
    realizable.append(max(len(c),n-len(c)))
print(max(realizable))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=[]
for j in range(0,n):
    l.append(input().split())
ans=0
for a in range(0,k):
     for b in range(0,a):
         i=0
         total=0
         while i<n:
           m=((int(l[i][0])-a)//k)%2
           h=((int(l[i][1])-b)//k)%2
           if ((m+h)%2==0 and str(l[i][2])=="W") or ((m+h)%2==1 and str(l[i][2])=="B"):
               total=total+1
               i=i+1
           else:
               i=i+1

         else:
              ans=max(ans,total,n-total)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=[]
for j in range(0,n):
    l.append(input().split())
ans=0
for a in range(0,k):
     for b in range(0,k):
         i=0
         total=0
         while i<n:
           m=(abs(int(l[i][0])-a)//k)%2
           h=(abs(int(l[i][1])-b)//k)%2
           if ((m+h)%2==0 and str(l[i][2])=="W") or ((m+h)%2==1 and str(l[i][2])=="B"):
               total=total+1
               i=i+1
           else:
               i=i+1

         else:
              ans=max(ans,total,n-total)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N,K=map(int,input().split())
#x,y,c=[],[],[]
lis=[[[0]*2 for _ in range(K)] for i in range(K)]
for i in range(N):
    x,y,c=input().split()
    x=int(x)
    y=int(y)
    """x.append(int(xx))
    y.append(int(yy))
    c.append(cc)"""
    if c=="B" :
        C=1
    if c=="W":
        C=0
    now=(x//K+y//K+C)%2
    lis[x%K][y%K][now]+=1
#print(lis)
"""for i in range(K):
    for j in range(1,K):
        lis[i][j][0]+=lis[i][j-1][0]
        lis[i][j][1]+=lis[i][j-1][1]
for i in range(1,K):
    lis[i][j][0]+=lis[i-1][j][0]
    lis[i][j][1]+=lis[i-1][j][1]"""
for i in range(K):
    for j in range(K):
        if i!=0 : lis[i][j][0]+=lis[i-1][j][0]
        if i!=0 : lis[i][j][1]+=lis[i-1][j][1]
        if j!=0 : lis[i][j][0]+=lis[i][j-1][0]
        if j!=0 : lis[i][j][1]+=lis[i][j-1][1]
        if i!=0 and j!=0:
            lis[i][j][0]-=lis[i-1][j-1][0]
            lis[i][j][1]-=lis[i-1][j-1][1]
#print(lis)
ans=0
for t in range(2):
    for i in range(K):
        for j in range(K):
            cnt=2*lis[i][j][t]+lis[-1][-1][t]-lis[i][-1][t]-lis[-1][j][t]\
                +lis[i][-1][1-t]+lis[j][-1][1-t]-2*lis[i][j][1-t]
            ans=max(ans,cnt)
"""
for i in range(K):
    for j in range(K):
        cnt=-2*lis[i][j]+lis[i][-1]+lis[-1][j]
        ans=max(ans,cnt)"""

print(ans)
#print(x,y,c)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N,K=map(int,input().split())
#x,y,c=[],[],[]
lis=[[[0]*2 for _ in range(K)] for i in range(K)]
ws=0
for i in range(N):
    x,y,c=input().split()
    x=int(x)
    y=int(y)
    """x.append(int(xx))
    y.append(int(yy))
    c.append(cc)"""
    if c=="B" :
        C=1
    if c=="W":
        C=0
    now=(x//K+y//K+C)%2
    lis[x%K][y%K][now]+=1
#print(lis)
for i in range(K):
    for j in range(1,K):
        lis[i][j][0]+=lis[i][j-1][0]
        lis[i][j][1]+=lis[i][j-1][1]
for i in range(1,K):
    lis[i][j][0]+=lis[i-1][j][0]
    lis[i][j][1]+=lis[i-1][j][1]
    """lis[i][j][0]-=lis[i-1][j-1][0]
    lis[i][j][1]-=lis[i-1][j-1][1]"""
#print(lis)
ans=0
for t in range(2):
    for i in range(K):
        for j in range(K):
            cnt=2*lis[i][j][t]+lis[-1][-1][t]-lis[i][-1][t]-lis[-1][j][t]\
                +lis[i][-1][1-t]+lis[j][-1][1-t]-2*lis[i][j][1-t]
            ans=max(ans,cnt)
"""
for i in range(K):
    for j in range(K):
        cnt=-2*lis[i][j]+lis[i][-1]+lis[-1][j]
        ans=max(ans,cnt)"""

print(ans)
#print(x,y,c)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N,K=map(int,input().split())
#x,y,c=[],[],[]
lis=[[0]*2*K for _ in range(2*K)]
los=0
for i in range(N):
    x,y,c=input().split()
    x=int(x)
    y=int(y)
    """x.append(int(xx))
    y.append(int(yy))
    c.append(cc)"""
    if c=="B":
        lis[x%(2*K)][y%(2*K)]+=1
    if c=="W":
        los+=1
        lis[x%(2*K)][y%(2*K)]-=1

cnt=los
for i in range(K):
    cnt+=sum(lis[i][:K])
    cnt+=sum(lis[i+K][K:2*K])
ans=cnt
for i in range(1,K):
    cnt+=sum(lis[K+i][0:K])-sum(lis[i][0:K])
    cnt+=sum(lis[(2*K+i)%(2*K)][K:2*K])-sum(lis[i+K][K:2*K])
    ans=max(ans,cnt,N-cnt)
    for j in range(1,K):
        cnt2=cnt+sum(lis[K+j][i:i+K])-sum(lis[j][i:i+K])
        cnt2+=sum(lis[(2*K+j)%(2*K)][i+K:(i+2*K)%(2*K)])-sum(lis[j+K][i+K:(i+2*K)%(2*K)])
        ans=max(ans,cnt2,N-cnt2)

print(ans)
#print(x,y,c)