Problem:


Score : 500 points

Problem Statement

AtCoDeer is thinking of painting an infinite two-dimensional grid in a checked pattern of side K.
Here, a checked pattern of side K is a pattern where each square is painted black or white so that each connected component of each color is a K × K square.
Below is an example of a checked pattern of side 3:

AtCoDeer has N desires.
The i-th desire is represented by x_i, y_i and c_i.
If c_i is B, it means that he wants to paint the square (x_i,y_i) black; if c_i is W, he wants to paint the square (x_i,y_i) white.
At most how many desires can he satisfy at the same time?

Constraints

1 ≤ N ≤ 10^5

1 ≤ K ≤ 1000

0 ≤ x_i ≤ 10^9

0 ≤ y_i ≤ 10^9

If i ≠ j, then (x_i,y_i) ≠ (x_j,y_j).

c_i is B or W.

N, K, x_i and y_i are integers.

Input

Input is given from Standard Input in the following format:

N K
x_1 y_1 c_1
x_2 y_2 c_2
:
x_N y_N c_N

Output

Print the maximum number of desires that can be satisfied at the same time.

Sample Input 1

4 3
0 1 W
1 2 W
5 3 B
5 4 B

Sample Output 1

4

He can satisfy all his desires by painting as shown in the example above.

Sample Input 2

2 1000
0 0 B
0 1 W

Sample Output 2

2

Sample Input 3

6 2
1 2 B
2 1 W
2 2 B
1 0 B
0 6 W
4 5 W

Sample Output 3

4



Sample input:
4 3
0 1 W
1 2 W
5 3 B
5 4 B


Sample output:
4

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from operator import add
N,K=map(int,input().split())
L=2*K
Map=[[0]*L for i in range(L)]

for i in range(N):
  x,y,c=input().split()
  x,y=int(x),int(y)
  if c=="W":
    x+=K
  x,y=x%L,y%L
  if y>=K:
    x,y=(x-K)%L,y-K
  Map[x][y]+=1
  Map[x][y-K]=-1
  if x!=K:
    Map[x-K][y-K]+=1
    Map[x-K][y]=-1
  if x>K:
    Map[0][y]+=1
    Map[0][y-K]-=1

Map=[accumulate(i) for i in Map]
Map=[accumulate(i) for i in zip(*Map)]
Map=list(map(list,zip(*Map)))
Map=[map(add, Map[i][:K], Map[i-K][K:]) for i in range(L)]

print(max(map(max,Map)))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
ss = [[0] * (4*K+2) for i in range(4*K+2)]


def query(x1, x2, y1, y2):
    return ss[x2][y2] - ss[x2][y1] - ss[x1][y2] + ss[x1][y1]


def main():
    for i in range(N):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == 'W':
            y += K

        x = (x+1) % (2*K+1)
        y = (y+1) % (2*K+1)

        ss[x][y] += 1
        ss[x+2*K][y] += 1
        ss[x][y+2*K] += 1
        ss[x+2*K][y+2*K] += 1

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

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

    ans = 0
    for i in range(1, 2*K+1):
        for j in range(1, 2*K+1):
            ans = max(ans, query(i, i+K, j, j+K)+query(i+K, i+2*K, j+K, j+2*K))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
ss = [[0] * (4*K+2) for i in range(4*K+2)]


def query(x1, x2, y1, y2):
    return ss[x2][y2] - ss[x2][y1] - ss[x1][y2] + ss[x1][y1]


def main():
    for i in range(N):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == 'W':
            y += K

        x = (x+1) % (2*K+1)
        y = (y+1) % (2*K+1)

        ss[x][y] += 1
        ss[x+2*K][y] += 1
        ss[x][y+2*K] += 1
        ss[x+2*K][y+2*K] += 1

    for i in range(4*K+1):
        for j in range(4*K+1):
            ss[i][j+1] += ss[i][j]

    for i in range(4*K+1):
        for j in range(4*K+1):
            ss[i+1][j] += ss[i][j]

    ans = 0
    for i in range(1, 2*K+1):
        for j in range(1, 2*K+1):
            ans = max(ans, query(i, i+K, j, j+K)+query(i+K, i+2*K, j+K, j+2*K))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
ss = [[0] * (4*K+1) for i in range(4*K+1)]


def query(x1, x2, y1, y2):
    return ss[x2][y2] - ss[x2][y1] - ss[x1][y2] + ss[x1][y1]


def main():
    for i in range(N):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == 'W':
            y += K

        x = (x+1) % (2*K+1)
        y = (y+1) % (2*K+1)

        ss[x][y] += 1
        ss[x+2*K][y] += 1
        ss[x][y+2*K] += 1
        ss[x+2*K][y+2*K] += 1

    for i in range(1, 4*K+1):
        for j in range(1, 4*K+1):
            ss[i][j] = ss[i][j-1] + ss[i][j]

    for i in range(1, 4*K+1):
        for j in range(1, 4*K+1):
            ss[i][j] = ss[i-1][j] + ss[i][j]

    ans = 0
    for i in range(1, 2*K+1):
        for j in range(1, 2*K+1):
            ans = max(ans, query(i, i+K, j, j+K)+query(i+K, i+2*K, j+K, j+2*K))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

B = [[0] * (2 * K + 1)] + [[0] + row for row in B]
ans = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        # 左上
        tmp = B[i - 1][j - 1]
        # 右上
        tmp += B[i - 1][2 * K] - B[i - 1][j + K - 1]
        # 真ん中
        tmp += B[i + K - 1][j + K - 1] - B[i - 1][j + K - 1] \
               - B[i + K - 1][j - 1] + B[i - 1][j - 1]
        # 左下
        tmp += B[2 * K][j - 1] - B[i + K - 1][j - 1]
        # 右下
        tmp += B[-1][-1] - B[i + K - 1][2 * K] - B[2 * K][j + K - 1] \
               + B[i + K - 1][j + K - 1]
        ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = [int(x) for x in input().split()]

table = [[0 for _ in range(K)] for _ in range(K)]

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

for i in range(K-1, 0 ,-1):
    for j in range(K-1, -1, -1):
        table[i-1][j] += table[i][j]

for i in range(K-1, -1 ,-1):
    for j in range(K-1, 0, -1):
        table[i][j-1] += table[i][j]

max_ac = abs(table[0][0])

for i in range(1,K):
    accept1 = table[0][0] -2 * table[i][0]
    accept2 = table[0][0] -2 * table[0][i]
    max_ac = max(max_ac, abs(accept1), abs(accept2))

for i in range(1, K):
    for j in range(1, K):
        accept = table[0][0] -2*table[i][0] -2*table[0][j] + 2*table[i][j]
        max_ac = max(max_ac, abs(accept))

print(int((max_ac+N)/2))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
k2=2*k
l=[[0 for _ in range(k2)] for _ in range(k2)]

def calc(x1,y1,x2,y2):
  if x1 > x2 or y1 > y2 or x1 < 0 or y1 < 0 or x2 < 0 or y2 < 0:
    return 0
  v=l[x2][y2]
  if y1>0:v-=l[x2][y1-1]
  if x1>0:v-=l[x1-1][y2]
  if x1>0 and y1>0:v+=l[x1-1][y1-1]
  return v

for _ in range(n):
  x,y,c=input().split()
  x,y=int(x),int(y)
  if c=="W":
    y+=k
  x%=k2
  y%=k2
  l[x][y]+=1
  
for i in range(k2):
  for j in range(1,k2):
    l[i][j]+=l[i][j-1]
for i in range(1,k2):
  for j in range(k2):
    l[i][j]+=l[i-1][j]

ans=0
for i in range(k):
  for j in range(k):
    v=0
    v+=calc(0,0,i-1,j-1)
    v+=calc(0,j+k,i-1,k2-1)
    v+=calc(i+k,0,k2-1,j-1)
    v+=calc(i,j,i+k-1,j+k-1)
    ans = max(ans,v,n-v)

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
k2=2*k
l=[[0 for _ in range(k2*2)] for _ in range(k2*2)]

for _ in range(n):
  x,y,c=input().split()
  x=int(x)
  y=int(y)
  if c=="W":
    x+=k
  x%=(2*k)
  y%=(2*k)
  l[y][x]+=1
  l[y+k][x+k]+=1
  l[y+k][x]-=1
  l[y][x+k]-=1

  l[y+k][x+k]+=1
  l[y+k2][x+k2]+=1
  l[y+k][x+k2]-=1
  l[y+k2][x+k]-=1

  
for i in range(k2*2):
  for j in range(1,k2*2):
    l[i][j]+=l[i][j-1]
for i in range(1,k2*2):
  for j in range(k2*2):
    l[i][j]+=l[i-1][j]

v=max(max(i) for i in l)
print(v)

Submission status: Wrong Answer

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

# (x, y) と (x, y+K)の色は必ず異なるので、すべて黒の要求に変換できる。
# 2Kずらすと必ず色が同じになるので、2Kでmodをとってよい。
for i in range(N):
    xi, yi, ci = input().split()
    if ci == "W":
        yi = int(yi) + K

    xi, yi = int(xi), int(yi)
    R.append([yi % K2, xi % K2])


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        # 問題によってイメージしやすいよう書き換えてください
        for x, y in points:
            self.G[x][y] += 1

        self.calc()

    def load_imos(self, points):
        # pointsは[[左上h, 左上w, 右下h, 右下w], ...]であること
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  # 左上
            if j2 + 1 < self.W:  # 右上
                self.G[i1][j2+1] -= 1
            if i2 + 1 < self.H:
                self.G[i2+1][j1] -= 1  # 左下
            if j2 + 1 < self.W and i2 + 1 < self.H:  # 右下
                self.G[i2+1][j2+1] += 1

        self.calc()

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x-1][y]

        for y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > i2 or j1 > j2 or i1 < 0 or j1 < 0 or i2 < 0 or j2 < 0:
            return 0
        elif i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1-1][j2] - self.G[i2][j1-1] + self.G[i1-1][j1-1]
        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1-1]
        elif j1 <= 0 < i1:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]


R2D = Ruisekiwa2D(K2, K2)
R2D.load(R)

ans = 0
for i in range(K):
    for j in range(K):
        tmp = 0
        tmp += R2D.get(0, 0, i-1, j-1)  # 左上
        tmp += R2D.get(0, j+K, i-1, K2-1)  # 右上
        tmp += R2D.get(i+K, j+K, K2-1, K2-1)  # 右下
        tmp += R2D.get(i+K, 0, K2-1, j-1)  # 左下
        tmp += R2D.get(i, j, i+K-1, j+K-1)  # 真ん中

        ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

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

# (x, y) と (x, y+K)の色は必ず異なるので、すべて黒の要求に変換できる。
# 2Kずらすと必ず色が同じになるので、2Kでmodをとってよい。
for i in range(N):
    xi, yi, ci = input().split()
    if ci == "W":
        yi = int(yi) + K

    xi, yi = int(xi), int(yi)
    R.append([yi % K2, xi % K2])


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        # 問題によってイメージしやすいよう書き換えてください
        for x, y in points:
            self.G[x][y] += 1

        self.calc()

    def load_imos(self, points):
        # pointsは[[左上h, 左上w, 右下h, 右下w], ...]であること
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  # 左上
            if j2 + 1 < self.W:  # 右上
                self.G[i1][j2+1] -= 1
            if i2 + 1 < self.H:
                self.G[i2+1][j1] -= 1  # 左下
            if j2 + 1 < self.W and i2 + 1 < self.H:  # 右下
                self.G[i2+1][j2+1] += 1

        self.calc()

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x-1][y]

        for y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > i2 or j1 > j2 or any(map(lambda x: x < 0, [i1, j1, i2, j2])):
            return 0
        elif i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1-1][j2] - self.G[i2][j1-1] + self.G[i1-1][j1-1]
        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1-1]
        elif j1 <= 0 < i1:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]


R2D = Ruisekiwa2D(K2, K2)
R2D.load(R)

ans = 0
for i in range(K):
    for j in range(K):
        tmp = 0
        tmp += R2D.get(0, 0, i-1, j-1)  # 左上
        tmp += R2D.get(0, j+K, i-1, K2-1)  # 右上
        tmp += R2D.get(i+K, j+K, K2-1, K2-1)  # 右下
        tmp += R2D.get(i+K, 0, K2-1, j-1)  # 左下
        tmp += R2D.get(i, j, i+K-1, j+K-1)  # 真ん中

        ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=[[0 for _ in range(1+2*k)] for _ in range(1+2*k)]
s=[[0 for _ in range(1+2*k)] for _ in range(1+2*k)]
for _ in range(n):
  x,y,c=input().split()
  x=int(x)
  y=int(y)
  if c=="B":
    l[(x+k)%(2*k)][y%(2*k)]+=1
  else:
    l[x%(2*k)][y%(2*k)]+=1
  
for i in range(2*k):
  for j in range(2*k):
    s[i][j]=l[i][j]
    if i>0:s[i][j]+=s[i-1][j]
    if j>0:s[i][j]+=s[i][j-1]
    if i>0 and j>0:s[i][j]-=s[i-1][j-1]
m=-1e9
for i in range(k):
  for j in range(k):
    v=s[i+k][j+k]
    if i>0:v-=s[i-1][j+k]
    if j>0:v-=s[i+k][j-1]
    if i>0 and j>0:v+=s[i-1][j-1]
    m=max(m,v)

print(m)

Submission status: Wrong Answer

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

# (x, y) と (x, y+K)の色は必ず異なるので、すべて黒の要求に変換できる。
# 2Kずらすと必ず色が同じになるので、2Kでmodをとってよい。
for i in range(N):
    xi, yi, ci = input().split()
    if ci == "W":
        yi = int(yi) + K

    xi, yi = int(xi), int(yi)
    R.append([xi % K2, yi % K2])


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        # 問題によってイメージしやすいよう書き換えてください
        for x, y in points:
            self.G[x][y] += 1

        self.calc()

    def load_imos(self, points):
        # pointsは[[左上h, 左上w, 右下h, 右下w], ...]であること
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  # 左上
            if j2 + 1 < self.W:  # 右上
                self.G[i1][j2+1] -= 1
            if i2 + 1 < self.H:
                self.G[i2+1][j1] -= 1  # 左下
            if j2 + 1 < self.W and i2 + 1 < self.H:  # 右下
                self.G[i2+1][j2+1] += 1

        self.calc()

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x-1][y]

        for y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1-1][j2] - self.G[i2][j1-1] + self.G[i1-1][j1-1]
        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1-1]
        elif j1 <= 0 < i1:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]


R2D = Ruisekiwa2D(K2, K2)
# imos法準備
R_imos = []
for x, y in R:
    R_imos.append([y, x, y+K, x+K])
R2D.load_imos(R_imos)

ans = 0
for i in range(K):
    for j in range(K):
        tmp = 0
        tmp += R2D.get(0, 0, i, j)  # 左上
        tmp += R2D.get(0, j+K, i, K2-1)  # 右上
        tmp += R2D.get(i+K, j+K, K2-1, K2-1)  # 右下
        tmp += R2D.get(i+K, 0, K2-1, j)  # 左下
        tmp += R2D.get(i, j, i+K-1, j+K-1)  # 真ん中

        ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

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

# (x, y) と (x, y+K)の色は必ず異なるので、すべて黒の要求に変換できる。
# 2Kずらすと必ず色が同じになるので、2Kでmodをとってよい。
for i in range(N):
    xi, yi, ci = input().split()
    if ci == "W":
        yi = int(yi) + K

    xi, yi = int(xi), int(yi)
    R.append([xi % K2, yi % K2])


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        # 問題によってイメージしやすいよう書き換えてください
        for x, y in points:
            self.G[x][y] += 1

        self.calc()

    def load_imos(self, points):
        # pointsは[[左上h, 左上w, 右下h, 右下w], ...]であること
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  # 左上
            if j2 + 1 < self.W:  # 右上
                self.G[i1][j2+1] -= 1
            if i2 + 1 < self.H:
                self.G[i2+1][j1] -= 1  # 左下
            if j2 + 1 < self.W and i2 + 1 < self.H:  # 右下
                self.G[i2+1][j2+1] += 1

        self.calc()

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x-1][y]

        for y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1-1][j2] - self.G[i2][j1-1] + self.G[i1-1][j1-1]
        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1-1]
        elif j1 <= 0 < i1:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]


R2D = Ruisekiwa2D(K2, K2)
# imos法準備
R_imos = []
for x, y in R:
    R_imos.append([y, x, y+K-1, x+K-1])
R2D.load_imos(R_imos)

ans = 0
for i in range(K):
    for j in range(K):
        tmp = 0
        tmp += R2D.get(0, 0, i, j)  # 左上
        tmp += R2D.get(0, j+K, i, K2-1)  # 右上
        tmp += R2D.get(i+K, j+K, K2-1, K2-1)  # 右下
        tmp += R2D.get(i+K, 0, K2-1, j)  # 左下
        tmp += R2D.get(i, j, i+K-1, j+K-1)  # 真ん中

        ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
def d_checker(N, K, Q):
    import itertools
    # マス(x,y)が白⇔マス(x,y+K)が黒なので、希望の色がすべて黒になるようにする
    # 市松模様の周期は2Kなので、x,y座標をそれぞれ2Kで剰余を取った座標と同一視できる
    mat = [[0]*(4*K+1) for _ in range(4*K+1)]
    total = [[0]*(4*K+1) for _ in range(4*K+1)]
    for x, y, c in Q:
        if c == 'W':
            y += K
        mat[x % (2*K)][y % (2*K)] += 1

    for x in range(4*K+1):
        for y in range(4*K+1):
            mat[x][y] = mat[x % (2*K)][y % (2*K)]

    for i in range(4*K+1):
        for j in range(4*K+1):
            total[i][j] = mat[i][j]
            if j-1 >= 0:
                total[i][j] += total[i][j-1]
            if i-1 >= 0:
                total[i][j] += total[i-1][j]
            if i-1 >= 0 and j-1 >= 0:
                total[i][j] -= total[i-1][j-1]

    def get(x1, y1, x2, y2, total):
        ret = total[x2][y2]
        if x1 > 0:
            ret -= total[x1-1][y2]
        if y1 > 0:
            ret -= total[x2][y1-1]
        if x1 > 0 and y1 > 0:
            ret += total[x1-1][y1-1]
        return ret

    ans = 0
    for x in range(2*K+1):
        for y in range(2*K+1):
            tmp = 0
            tmp += get(x, y, x+K-1, y+K-1, total)
            tmp += get(x+K, y+K, x+2+K-1, y+2*K-1, total)
            ans = max(ans, tmp)

    return ans

N, K = [int(i) for i in input().split()]
Q = [(int(x), int(y), c)
    for x, y, c in [input().split() for i in range(N)]]
print(d_checker(N, K, Q))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
table=[[0]*K for i in range(K)]#W=1
C=0
for i in range(N):
    x,y,z=input().split()
    x = int(x)
    y=int(y)
    if z=='B':
        y +=K
    x %=(2*K)
    y %=(2*K)
    t = (x//K +y//K)%2
    x%= K
    y%=K
    if t:
        table[y][x]-=1
    else:
        table[y][x]+=1
        C+=1
B=N-C
#print(table)
pr=[[0]*(K+1) for i in range(K)]
for i in range(K):
    for j in range(K):
        pr[j][i+1]=pr[j][i]+table[j][i]
#print(pr)
pr2=[[0]*(K+1) for i in range(K+1)]
for j in range(K):
    for i in range(K):
        pr2[j+1][i+1]=pr2[j][i+1]+pr[j][i+1]
#print(pr2)
ans = 0
for i in range(K+1):
    for j in range(K+1):
        #s=pr2[K][K]-pr2[i-1][K] -pr2[K][j-1]+2*pr2[i-1][j-1]
        s =pr2[i][K] +pr2[K][j]-2*pr2[i][j]
        #白で塗った時に差し引き難点もらえるか
        #t=pr2[K][K]-s#黒で塗る
        #print(s,t,s-t,C-s)
        ans = max(ans,C-s)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def cumulative_sum_2d(a):
    h, w = len(a), len(a[0])
    for i in range(1, h):
        for j in range(w):
            a[i][j] += a[i-1][j]
    for i in range(h):
        for j in range(1, w):
            a[i][j] += a[i][j-1]

def solve(f):
    n, k = f.read_int_list()
    b = [[0] * k for _ in xrange(k)]
    w = [[0] * k for _ in xrange(k)]
    for i in xrange(n):
        x, y, c = f.read_str().split()
        x, y = int(x)%(2*k), int(y)%(2*k)
        sgn = 1 if c == 'B' else -1
        if x >= k: sgn *= -1
        if y >= k: sgn *= -1
        if sgn == 1:
            b[x-k][y-k] += 1
        else:
            w[x-k][y-k] += 1

    cumulative_sum_2d(b)
    cumulative_sum_2d(w)

    ans = 0
    for xi in xrange(k):
        for yi in xrange(k):
            res = 0
            if xi == yi == 0:
                res += b[k-1][k-1]
            elif xi == 0:
                res += b[k-1][k-1] - b[k-1][yi-1]
                res += w[k-1][yi-1]
            elif yi == 0:
                res += b[k-1][k-1] - b[xi-1][k-1]
                res += w[xi-1][yi-1]
            else:
                res += b[k-1][k-1] - b[xi-1][k-1] - b[k-1][yi-1] + b[xi-1][yi-1]
                res += b[xi-1][yi-1]
                res += w[xi-1][k-1] - w[xi-1][yi-1]
                res += w[k-1][yi-1] - w[xi-1][yi-1]
            ans = max(res, ans)

    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, k = map(int, input().split())
k2 = k*2
counter = np.zeros((k2, k2), dtype=int)
for _ in range(n):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == 'W':
        x += k
    x = x % k2
    y = y % k2
    if x >= k-1 and y >= k-1:
        counter[x-k+1:x+1, y-k+1:y+1] += 1
    elif x >= k-1 and y < k-1:
        counter[x-k+1:x+1, :y+1] += 1
        counter[x-k+1:x+1, -(k-y):] += 1
    elif x < k-1 and y >= k-1:
        counter[:x+1, y-k+1:y+1] += 1
        counter[-(k-x):, y-k+1:y+1] += 1
    else:
        counter[:x+1, :y+1] += 1
        counter[-(k-x):, -(k-y)] += 1
print(counter.max())

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def reads():
  return [int(x) for x in input().split()]

(N, K) = reads()

L = K

board = [[0] * K for _ in range(K)]

NW = 0
for _ in range(N):
    (x, y, c) = input().split()
    (x, y) = (int(x), int(y))
    c = (x // K + y // K + int(c == "W")) & 1 # W -> 1, B -> 0
    (x, y) = (x % K, y % K)
    NW += c
    board[y][x] += 1 if c == 1 else -1 # W - B
NB = N - NW

psumr = [[0] * (K+1) for _ in range(K)]

for i in range(K):
    for j in range(K):
        psumr[i][j+1] = psumr[i][j] + board[i][j]

psum = [[0] * (K+1) for _ in range(K+1)]

for i in range(K):
    for j in range(K):
        psum[i+1][j+1] = psum[i][j+1] + psumr[i][j+1]

result = 0
for i in range(K+1):
    for j in range(K+1):
        summ = psum[i][K] + psum[K][j] - psum[i][j]
        result = max(result, NB + summ, NW - summ)
print(result)

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def reads():
  return [int(x) for x in input().split()]

(N, K) = reads()

L = K

board = [[0] * K for _ in range(K)]

NW = 0
for _ in range(N):
    (x, y, c) = input().split()
    (x, y) = (int(x), int(y))
    c = (x // K + y // K + int(c == "W")) & 1 # W -> 1, B -> 0
    (x, y) = (x % K, y % K)
    NW += c
    board[y][x] += 1 if c == 1 else -1 # W - B
NB = N - NW

psumr = [[0] * (K+1) for _ in range(K)]

for i in range(K):
    for j in range(K):
        psumr[i][j+1] = psumr[i][j] + board[i][j]

psum = [[0] * (K+1) for _ in range(K+1)]

for i in range(K):
    for j in range(K):
        psum[i+1][j+1] = psum[i][j+1] + psumr[i][j+1]

S = sum(board[i][j] for i in range(K) for j in range(K))
assert sum(board[i][j] for i in range(K) for j in range(K)) == NW - NB

result = 0
for i in range(K+1):
    for j in range(K+1):
        summ = psum[i][K] + psum[K][j] - psum[i][j]
        result = max(result, NB + summ, 2 * NW - NB - summ)
print(result)

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def reads():
  return [int(x) for x in input().split()]

(N, K) = reads()

L = K

board = [[0] * K for _ in range(K)]

NW = 0
for _ in range(N):
    (x, y, c) = input().split()
    (x, y) = (int(x), int(y))
    c = (x // K + y // K + int(c == "W")) & 1 # W -> 1, B -> 0
    (x, y) = (x % K, y % K)
    NW += c
    board[y][x] += 1 if c == 1 else -1 # W - B
NB = N - NW

psumr = [[0] * (K+1) for _ in range(K)]

for i in range(K):
    for j in range(K):
        psumr[i][j+1] = psumr[i][j] + board[i][j]

psum = [[0] * (K+1) for _ in range(K+1)]

for i in range(K):
    for j in range(K):
        psum[i+1][j+1] = psum[i][j+1] + psumr[i][j+1]

S = sum(board[i][j] for i in range(K) for j in range(K))
assert sum(board[i][j] for i in range(K) for j in range(K)) == NW - NB

result = 0
for i in range(K):
    for j in range(K):
        summ = psum[i][K] + psum[K][j] - psum[i][j]
        result = max(result, NB + summ, 2 * NW - NB - summ)
print(result)

Submission status: Wrong Answer

Solution code:
import numpy as np
temp=input().split(" ")
n=int(temp[0])
k=int(temp[1])
k2=2*k
ans=0

tileb=[[0 for i in range(k2*2)] for j in range(k2*2)]
for i in range(n):
    temp=input().split(" ")
    x=int(temp[0])
    y=int(temp[1])
    c=temp[2]
    
    tempx=x%(k2)
    if c=='B':  
        tempy=y%(k2)
        
    elif c=='W':  
        tempy=(y+k)%(k2)

    tileb[tempy][tempx]+=1
    tileb[tempy+k2][tempx]+=1
    tileb[tempy][tempx+k2]+=1
    tileb[tempy+k2][tempx+k2]+=1
        

ruisekiwa=[[0 for i in range(k2)] for j in range(k2)]
# for x in range(0,k2):
#     ruisekiwa[0][x]=tileb[0][x]

# ans=0
# for y in range(0,k2*2):
#     for x in range(1,k2*2):
#         tileb[y][x]+=tileb[y][x-1]

# for x in range(0,k2*2):
#     for y in range(1,k2*2):
#         tileb[y][x]+=tileb[y-1][x]

def nijiruisekiwa(x,y,k): #左下(x,y) 長さkの正方形領域の和
    global tileb
    if x==0 and y==0:     
        return tileb[y+k-1][x+k-1]
    if y==0:     
        return tileb[y+k-1][x+k-1]-tileb[y+k-1][x-1]
    if x==0:     
        return tileb[y+k-1][x+k-1]-tileb[y-1][x+k-1]
    else:     
        return tileb[y+k-1][x+k-1]-tileb[y+k-1][x-1]-tileb[y-1][x+k-1]+tileb[y-1][x-1]

for x in range(0,k2):
    for y in range(0,k2):
        temp=0
        a=nijiruisekiwa(x,y,k)
        b=nijiruisekiwa(x+k,y+k,k)

        temp=a+b
      #  print("temp="+str(temp))

        if temp>ans:
            # print(a)
            # print(b)
            # print("x={0}  y={1}  ".format(x,y))
            ans=temp
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
temp=input().split(" ")
n=int(temp[0])
k=int(temp[1])
k2=2*k
tileb=[[0 for i in range(k2*2)] for j in range(k2*2)]
for i in range(n):
    temp=input().split(" ")
    x=int(temp[0])
    y=int(temp[1])
    c=temp[2]
    tempx=x%(k2)
    if c=='B':  
        tempy=y%(k2)
        
    elif c=='W':  
        tempy=(y+k)%(k2)

    tileb[tempy][tempx]+=1
    tileb[tempy+k2][tempx]+=1
    tileb[tempy][tempx+k2]+=1
    tileb[tempy+k2][tempx+k2]+=1
        

ruisekiwa=[[0 for i in range(k2)] for j in range(k2)]
for x in range(0,k2):
    ruisekiwa[0][x]=tileb[0][x]

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

for x in range(0,k2+k):
    for y in range(1,k2+k):
        tileb[y][x]+=tileb[y-1][x]

# tileb=np.array(tileb)
# tileb=tileb.cumsum(0)
# tileb=tileb.cumsum(1)
# tileb=list(tileb)
def nijiruisekiwa(x,y,k): #左下(x,y) 長さkの正方形領域の和
    global tileb
    if x==0 and y==0:     
        return tileb[y+k-1][x+k-1]
    if y==0:     
        return tileb[y+k-1][x+k-1]-tileb[y+k-1][x-1]
    if x==0:     
        return tileb[y+k-1][x+k-1]-tileb[y-1][x+k-1]
    else:     
        return tileb[y+k-1][x+k-1]-tileb[y+k-1][x-1]-tileb[y-1][x+k-1]+tileb[y-1][x-1]

for x in range(0,k2):
    for y in range(0,k2):
        temp=0
        a=nijiruisekiwa(x,y,k)
        b=nijiruisekiwa(x+k,y+k,k)

        temp=a+b
      #  print("temp="+str(temp))

        if temp>ans:
            # print(a)
            # print(b)
            # print("x={0}  y={1}  ".format(x,y))
            ans=temp
print(ans)

Submission status: Wrong Answer

Solution code:
temp=input().split(" ")
n=int(temp[0])
k=int(temp[1])
k2=2*k
tileb=[[0 for i in range(k2*2)] for j in range(k2*2)]
for i in range(n):
    temp=input().split(" ")
    x=int(temp[0])
    y=int(temp[1])
    c=temp[2]
    if c=='B':  
        tileb[y%(k2)][x%(k2)]+=1
    elif c=='W':  
        tileb[(y+k)%k2][x%k2]+=1
#ruisekiwa=[[0 for i in range(k2)] for j in range(k2)]
# for x in range(0,k2):
#     ruisekiwa[0][x]=tileb[0][x]

ans=0
for y in range(0,k2*2):
    for x in range(1,k2*2):
        tileb[y][x]+=tileb[y][x-1]

for x in range(0,k2*2):
    for y in range(1,k2*2):
        tileb[y][x]+=tileb[y-1][x]
# print(tileb)

def nijiruisekiwa(x,y,k): #左下(x,y) 長さkの正方形領域の和
    global tileb
    if x==0 and y==0:     
        return tileb[y+k-1][x+k-1]
    if y==0:     
        return tileb[y+k-1][x+k-1]-tileb[y+k-1][x-1]
    if x==0:     
        return tileb[y+k-1][x+k-1]-tileb[y-1][x+k-1]
    else:     
        return tileb[y+k-1][x+k-1]-tileb[y+k-1][x-1]-tileb[y-1][x+k-1]+tileb[y-1][x-1]
for x in range(0,k2):
    for y in range(0,k2):
        temp=0
        a=nijiruisekiwa(x,y,k)
        b=nijiruisekiwa(x+k,y+k,k)

        temp=a+b
        if temp>ans:
            # print(a)
            # print(b)
            # print("x={0}  y={1}  ".format(x,y))
            # print(temp)
            ans=temp
print(ans)