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

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n, k = map(int, input().split())
    k2 = k * 2
    t = [[0] * k2 for _ in range(k2)]
    for _ in range(n):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == "W": x += k
        x %= k2
        y %= k2
        t[x][y] += 1
        x = (x + k) % k2
        y = (y + k) % k2
        t[x][y] += 1
    # p2D(t)
    # print()
    for i in range(k2):
        ti = t[i]
        for j in range(1, k2):
            ti[j] += ti[j - 1]
    for j in range(k2):
        for i in range(1, k2):
            t[i][j] += t[i - 1][j]
    # p2D(t)
    ans = 0
    for i in range(k - 1, k2):
        for j in range(k - 1, k2):
            cur = t[i][j]
            if i - k >= 0: cur -= t[i - k][j]
            if j - k >= 0: cur -= t[i][j - k]
            if i >= k and j >= k: cur += t[i - k][j - k]
            if cur > ans: ans = cur
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n, k = map(int, input().split())
    k4 = k * 4
    k3 = k * 3
    k2 = k * 2
    t = [[0] * k2 for _ in range(k2)]
    for _ in range(n):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == "W": x += k
        x %= k2
        y %= k2
        t[x][y] += 1
        if y < k and x < k: t[x + k][y + k] += 1
        if x < k: t[x + k][y] -= 1
        if y < k: t[x][y + k] -= 1
        x = (x + k) % k2
        y = (y + k) % k2
        t[x][y] += 1
        if y < k and x < k: t[x + k][y + k] += 1
        if x < k: t[x + k][y] -= 1
        if y < k: t[x][y + k] -= 1
    # p2D(t)
    for i in range(k2):
        ti = t[i]
        for j in range(1, k2):
            ti[j] += ti[j - 1]
    for j in range(k2):
        for i in range(1, k2):
            t[i][j] += t[i - 1][j]
    # p2D(t)
    print(max(max(tk) for tk in t))

main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n, k = map(int, input().split())
    k4 = k * 4
    k3 = k * 3
    k2 = k * 2
    t = [[0] * (k3+5) for _ in range(k3+5)]
    for _ in range(n):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == "W": x += k
        x %= k2
        y %= k2
        t[x][y] += 1
        t[x + k][y + k] += 1
        t[x + k][y] -= 1
        t[x][y + k] -= 1
        x=(x+k)%k2
        y=(y+k)%k2
        t[x][y] += 1
        t[x + k][y + k] += 1
        t[x + k][y] -= 1
        t[x][y + k] -= 1
    #p2D(t)
    for i in range(k3+5):
        ti=t[i]
        for j in range(1, k3+5):
            ti[j] += ti[j - 1]
    for j in range(k3+5):
        for i in range(1, k3+5):
            t[i][j] += t[i - 1][j]
    #p2D(t)
    print(max(max(tk) for tk in t))

main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n, k = map(int, input().split())
    k4 = k * 4
    k3 = k * 3
    k2 = k * 2
    t = [[0] * k3 for _ in range(k3)]
    for _ in range(n):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == "W": x += k
        x %= k2
        y %= k2
        t[x][y] += 1
        t[x + k][y + k] += 1
        t[x + k][y] -= 1
        t[x][y + k] -= 1
        x=(x+k)%k2
        y=(y+k)%k2
        t[x][y] += 1
        t[x + k][y + k] += 1
        t[x + k][y] -= 1
        t[x][y + k] -= 1
    #p2D(t)
    for i in range(k3):
        ti=t[i]
        for j in range(1, k3):
            ti[j] += ti[j - 1]
    for j in range(k3):
        for i in range(1, k3):
            t[i][j] += t[i - 1][j]
    #p2D(t)
    print(max(max(tk) for tk in t))

main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
xyc=[list(input().split()) for i in range(n)]
data=[[[] for i in range(k)] for j in range(k)]
B=[[0]*k for i in range(k)]
W=[[0]*k for i in range(k)]
for u in xyc:
    x=int(u[0])
    y=int(u[1])
    c=u[2]
    a,b=x%k,y%k
    if (x//k+y//k)%2==0:
        if c=="B":
            B[a][b]+=1
        else:
            W[a][b]+=1
    else:
        if c=="B":
            W[a][b]+=1
        else:
            B[a][b]+=1
lst=[[0]*k for i in range(k)]
li=[[0]*k for i in range(k)]
for i in range(k):
    lst[i][0]=B[i][0]
    li[i][0]=W[i][0]
    for j in range(1,k):
        lst[i][j]=lst[i][j-1]+B[i][j]
        li[i][j]=li[i][j-1]+W[i][j]
for i in range(1,k):
    for j in range(k):
        lst[i][j]+=lst[i-1][j]
        li[i][j]+=li[i-1][j]
det=[[0]*k for i in range(k)]
den=[[0]*k for i in range(k)]
for i in range(k):
    i=k-1-i
    det[i][k-1]=B[i][k-1]
    den[i][k-1]=W[i][k-1]
    for j in range(1,k):
        j=k-j-1
        det[i][j]=det[i][j+1]+B[i][j]
        den[i][j]=den[i][j+1]+W[i][j]
for i in range(1,k):
    i=k-i-1
    for j in range(k):
        j=k-j-1
        det[i][j]+=det[i+1][j]
        den[i][j]+=den[i+1][j]
bcount=lst[k-1][k-1]
wcount=li[k-1][k-1]
ans=abs(bcount-wcount)
for i in range(k-1):
    for j in range(k-1):
        o=lst[i][j]+det[i+1][j+1]
        p=li[i][j]+den[i+1][j+1]
        ans=max(ans,o+wcount-p,bcount-o+p)
for i in range(k-1):
    o=lst[k-1][i]
    O=lst[i][k-1]
    p=li[k-1][i]
    P=li[i][k-1]
    ans=max(ans,bcount-o+p,wcount-p+o)
    ans=max(ans,bcount-O+P,wcount-P+O)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
counts = [[0] * 2*K for _ in range(2*K)]

for _ in range(N):
  x, y, t = input().split()
  if t == 'B':
    x = int(x) + K
  counts[int(x)%(2*K)][int(y)%(2*K)] += 1
max_c = 0
for i in range(K):
  sum_c = 0
  for idx, row in enumerate(counts):
    if idx < i:
      sum_c += sum(row[K:])
    elif idx < i + K:
      sum_c += sum(row[:K])
    else:
      sum_c += sum(row[K:])
  max_c = max(max_c, sum_c)
  for j in range(K):
    minus = plus = 0
    for idx, row in enumerate(counts):
      if idx < i:
        minus += row[j+K]
        plus += row[j]
      elif idx < i + K:
        minus += row[j]
        plus += row[j+K]
      else:
        minus += row[j+K]
        plus += row[j]
    sum_c = sum_c-minus+plus
    max_c = max(max_c, sum_c)
print(max_c)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
paints = [list(input().split()) for _ in range(N)]
counts = [[0] * 2*K for _ in range(2*K)]

for paint in paints:
  x, y, t = int(paint[0]), int(paint[1]), paint[2]
  if t == 'B':
    x += K
  counts[x%(2*K)][y%(2*K)] += 1
max_c = 0
for i in range(K):
  sum_c = 0
  for idx, row in enumerate(counts):
    if idx < i:
      sum_c += sum(row[K:])
    elif idx < i + K:
      sum_c += sum(row[:K])
    else:
      sum_c += sum(row[K:])
  max_c = max(max_c, sum_c)
  for j in range(K):
    minus = plus = 0
    for idx, row in enumerate(counts):
      if idx < i:
        minus += row[j+K]
        plus += row[j]
      elif idx < i + K:
        minus += row[j]
        plus += row[j+K]
      else:
        minus += row[j+K]
        plus += row[j]
    sum_c = sum_c-minus+plus
    max_c = max(max_c, sum_c)
print(max_c)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
l = []
for i in range(n):
    a = list(input().split())
    l.append(a)
l1 = [[0,1,5],[0,1,2],[4,5,0]]
l2 = [[2,3,4],[3,4,5],[1,2,3]]
count = [0 for i in range(18)]
for i in range(n):
    p = int(l[i][0])
    q = int(l[i][1])
    if p < 0:
        p1 = 6 - ((abs(p)) % 6)
        if p1 == 6:
            p1 = 0
    else:
        p1 = p % 6
    if q < 0:
        q1 = 6 - ((abs(q)) % 6)
        if q1 == 6:
            q1 = 0
    else:
        q1 = q % 6
    c = 0
    for j in range(3):
        for x in range(3):
            if p1 in l1[j]:
                if q1 in l1[x]:
                    if l[i][2] == "W":
                        count[c] += 1
                    else:
                        count[9+c] += 1
                else:
                    if l[i][2] == "B":
                        count[c] += 1
                    else:
                        count[9+c] += 1
            else:
                if q1 in l1[x]:
                    if l[i][2] == "B":
                        count[c] += 1
                    else:
                        count[9+c] += 1
                else:
                    if l[i][2] == "W":
                        count[c] += 1
                    else:
                        count[9+c] += 1
            c += 1
print(max(count))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class ACC_2D:
    """
    二次元累積わ
    """

    def __init__(self, W, H):
        """
        W:幅
        H:高さ
        """

        self.W = W
        self.H = H
        self.mat = [[0]*(W+1) for _ in range(H+1)]

    def add(self, row, col, val):
        """
        matの値を変更する(初期化)
        row:たて(0<=row<H)
        col:横(0<=col<W)
        val:mat[row][col]を初期化する値
        mat[row][col]+=val
        """
        self.mat[row][col] += val

    def build(self):
        """
        累積和を計算する
        """
        for row in range(1, self.H+1):
            for col in range(1, self.W+1):
                self.mat[row][col] += self.mat[row][col-1] + \
                    self.mat[row-1][col] - self.mat[row-1][col-1]

    def get_val(self, g_row, g_col, s_row, s_col):
        """
        ２点で囲まれる長方形の、累積和を求める
        gx,gyは含まれない
        """
        return self.mat[g_row][g_col] - self.mat[s_row][g_col] - self.mat[g_row][s_col] + self.mat[s_row][s_col]


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

    ACC = ACC_2D(K2, K2)

    # handle input
    # 全てを2K*2Kに圧縮する
    for _ in range(N):
        x, y, s = input().split()
        # 2K * 2Kに収める
        x = int(x)
        y = int(y)
        if s == "W":
            y += K
        x %= K2
        y %= K2

        ACC.add(x, y, 1)

    # 累積和をとる
    ACC.build()

    ans = 0
    for row in range(K + 1):
        for col in range(K + 1):
            d = ACC.get_val(row+K, col, row, 0)
            d += ACC.get_val(row, col+K, 0, col)
            d += ACC.get_val(K2, col+K, row+K, col)
            d += ACC.get_val(row+K, K2, row, col+K)
            ans = max(ans, d, N-d)
    print(ans)


solve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class ACC_2D:
    """
    二次元累積わ
    """

    def __init__(self, W, H):
        """
        W:幅
        H:高さ
        """

        self.W = W
        self.H = H
        self.mat = [[0]*(W+1) for _ in range(H+1)]

    def add(self, row, col, val):
        """
        matの値を変更する(初期化)
        row:たて(0<=row<H)
        col:横(0<=col<W)
        val:mat[row][col]を初期化する値
        mat[row][col]+=val
        """
        self.mat[row][col] += val

    def build(self):
        """
        累積和を計算する
        """
        for row in range(1, self.H+1):
            for col in range(1, self.W+1):
                self.mat[row][col] += self.mat[row][col-1] + \
                    self.mat[row-1][col] - self.mat[row-1][col-1]

    def get_val(self, g_row, g_col, s_row, s_col):
        """
        ２点で囲まれる長方形の、累積和を求める
        gx,gyは含まれない
        """
        return self.mat[g_row][g_col] - self.mat[s_row][g_col] - self.mat[g_row][s_col] + self.mat[s_row][s_col]


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

    ACC = ACC_2D(K2, K2)

    # handle input
    # 全てを2K*2Kに圧縮する
    for _ in range(N):
        x, y, s = input().split()
        # 2K * 2Kに収める
        x = int(x)
        y = int(y)
        if s == "W":
            y += K
        x %= K2
        y %= K2

        ACC.add(x, y, 1)

    # 累積和をとる
    ACC.build()

    ans = 0
    for row in range(K + 1):
        for col in range(K + 1):
            d = ACC.get_val(row+K, col, row, 0)
            d += ACC.get_val(row, col+K, 0, col)
            d += ACC.get_val(-1, col+K, row+K, col)
            d += ACC.get_val(row+K, -1, row, col+K)
            ans = max(ans, d)
            ans = max(ans, N - d)
    print(ans)


solve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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

    grid = [[0]*(K2+1) for _ in range(K2+1)]

    # handle input
    # 全てを2K*2Kに圧縮する
    for _ in range(N):
        x, y, s = input().split()
        # 2K * 2Kに収める
        x = int(x)
        y = int(y)
        if s == "W":
            y += K
        x %= K2
        y %= K2

        grid[x][y] += 1

    # 累積和をとる
    for row in range(1, K2+1):
        for col in range(1, K2+1):
            grid[row][col] += grid[row-1][col] + \
                grid[row][col-1] - grid[row-1][col-1]

    ans = 0
    for row in range(K + 1):
        for col in range(K + 1):
            d = grid[row+K][col] + grid[row][0] - \
                grid[row][col] - grid[row+K][0]

            d += grid[row][col+K] + grid[0][col] - \
                grid[0][col+K]-grid[row][col]

            d += grid[row][col+K] + grid[row+K][-1] - \
                grid[row+K][col+K] - grid[row][-1]

            d += grid[row+K][col] + grid[-1][col+K] -\
                grid[-1][col] - grid[row+K][col+K]
            ans = max(ans, d)
            ans = max(ans, N - d)
    print(ans)


solve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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

    grid = [[0]*(K2+1) for _ in range(K2+1)]

    # handle input
    # 全てを2K*2Kに圧縮する
    for _ in range(N):
        x, y, s = input().split()
        # 2K * 2Kに収める
        x = int(x)
        y = int(y)
        if s == "W":
            y += K
        x %= K2
        y %= K2

        grid[x][y] += 1

    # 累積和をとる
    for row in range(1, K2+1):
        for col in range(1, K2+1):
            grid[row][col] += grid[row-1][col] + \
                grid[row][col-1] - grid[row-1][col-1]

    ans = 0
    for i in range(K + 1):
        for j in range(K + 1):
            d = grid[i][j]
            d += grid[i + K][j + K] - grid[i][j + K] - \
                grid[i + K][j] + grid[i][j]
            d += grid[2 * K][j] - grid[i + K][j]
            d += grid[i][2 * K] - grid[i][j + K]
            d += grid[2 * K][2 * K] - grid[2 * K][j + K] - \
                grid[i + K][2 * K] + grid[i + K][j + K]
            ans = max(ans, d)
            ans = max(ans, N - d)
    print(ans)


solve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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

    grid = [[0]*(K2+1) for _ in range(K2+1)]

    # handle input
    # 全てを2K*2Kに圧縮する
    for _ in range(N):
        x, y, s = input().split()
        # 2K * 2Kに収める
        x = int(x)
        y = int(y)
        if s == "W":
            y += K
        x %= K2
        y %= K2

        grid[x][y] += 1

    # 累積和をとる
    for row in range(1, K2+1):
        for col in range(1, K2+1):
            grid[row][col] += grid[row-1][col] + \
                grid[row][col-1] - grid[row-1][col-1]

    ans = 0
    for row in range(K2):
        for col in range(K2):
            down_lim = (row % K)+K
            left_lim = (col % K)+K
            upper_left = grid[row][col] - \
                grid[row][0]-grid[0][col]+grid[0][0]
            down_right = grid[-1][-1]-grid[down_lim][-1] - \
                grid[-1][left_lim]+grid[down_lim][left_lim]
            upper_right = grid[row][-1] - \
                grid[0][-1]-grid[row][left_lim]+grid[0][left_lim]
            down_left = grid[col][-1]-grid[row][-1] - \
                grid[row][-1]+grid[row][0]
            center = grid[down_lim][left_lim]-grid[down_lim][col] - \
                grid[row][left_lim]+grid[row][col]
            tmp = upper_left+down_right+center+down_left+upper_right
            if row < K and col < K or row <= K and col >= K:
                tmp = tmp
            else:
                tmp = N - tmp

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


solve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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

    grid = [[0]*(K2+1) for _ in range(K2+1)]

    # handle input
    # 全てを2K*2Kに圧縮する
    for _ in range(N):
        x, y, s = input().split()
        # 2K * 2Kに収める
        x = int(x)
        y = int(y)
        if s == "W":
            y += K
        x %= K2
        y %= K2

        grid[x][y] += 1

    # 累積和をとる
    for row in range(1, K2+1):
        for col in range(1, K2+1):
            grid[row][col] += grid[row-1][col] + \
                grid[row][col-1] - grid[row-1][col-1]

    ans = 0
    for row in range(K2):
        for col in range(K2):
            tmp = 0
            down_lim = min(row+K, K2)
            left_lim = min(col+K, K2)
            upper_left = grid[row][col]-grid[row][0]-grid[0][col]+grid[0][0]
            down_right = grid[-1][-1]-grid[down_lim][-1] - \
                grid[-1][left_lim]+grid[down_lim][left_lim]
            center = grid[down_lim][left_lim]-grid[down_lim][col] - \
                grid[row][left_lim]+grid[row][col]
            tmp = upper_left+down_right+center
            ans = max(ans, tmp)
    print(ans)


solve()

Submission status: Wrong Answer

Solution code:
# 入力
N, K = map(int, input().split())
x, y, c = zip(*(((int(x), int(y), c)
              for x, y, c in (input().split() for _ in range(N)))))

K2 = 2 * K

# 各クエリを(0, 0)から(K -1, K - 1) の矩形にマッピングし、各マスの個数をカウント
cs = [
    [
        0
        for _ in range(K2)
    ]
    for _ in range(K2)
]
for i, j, k in zip(x, y, c):
    cs[(i + K * (k == 'W')) % K2][j % K2] += 1

# dp[i][j] はマス(i, j) から K*K のマスを黒で塗るときに叶えられる要望の数
dp = [
    [
        0
        for _ in range(K2)
    ]
    for _ in range(K2)
]
# 累積和を用いて解を求める
dp[0][0] = sum(
    cs[i][j]
    for i in range(K)
    for j in range(K)
)
for i in range(1, K + 1):
    dp[i][0] = dp[i - 1][0] + sum(
        cs[i + K - 1][j]
        for j in range(K)
    ) - sum(
        cs[i - 1][j]
        for j in range(K)
    )
    dp[0][i] = dp[0][i - 1] + sum(
        cs[j][i + K - 1]
        for j in range(K)
    ) - sum(
        cs[j][i - 1]
        for j in range(K)
    )
for i in range(K + 1, K2):
    dp[i][0] = dp[i - 1][0] + sum(
        cs[i - (K + 1)][j]
        for j in range(K)
    ) - sum(
        cs[i - 1][j]
        for j in range(K)
    )
    dp[0][i] = dp[0][i - 1] + sum(
        cs[j][i - (K + 1)]
        for j in range(K)
    ) - sum(
        cs[j][i - 1]
        for j in range(K)
    )
for i in range(1, K + 1):
    for j in range(1, K + 1):
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - \
            dp[i - 1][j - 1] + \
            cs[i + K - 1][j + K - 1] + \
            cs[i - 1][j - 1] - \
            cs[i - 1][j + K - 1] - \
            cs[i + K - 1][j - 1]
    for j in range(K + 1, K2):
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - \
            dp[i - 1][j - 1] + \
            cs[i + K - 1][j - (K + 1)] + \
            cs[i - 1][j - 1] - \
            cs[i - 1][j - (K + 1)] - \
            cs[i + K - 1][j - 1]
for i in range(K + 1, 2 * K):
    for j in range(1, K + 1):
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - \
            dp[i - 1][j - 1] + \
            cs[i - (K + 1)][j + K - 1] + \
            cs[i - 1][j - 1] - \
            cs[i - 1][j + K - 1] - \
            cs[i - (K + 1)][j - 1]
    for j in range(K + 1, K2):
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - \
            dp[i - 1][j - 1] + \
            cs[i - (K + 1)][j - (K + 1)] + \
            cs[i - 1][j - 1] - \
            cs[i - 1][j - (K + 1)] - \
            cs[i - (K + 1)][j - 1]
# 全通りの塗り方を試し、解を求める
ans = max(
    max(
        dp[i][j] + dp[i + K][j + K]
        for i in range(K)
        for j in range(K)
    ),
    max(
        dp[i][j] + dp[i - K][j - K]
        for i in range(K, K2)
        for j in range(K, K2)
    )
)

# 出力
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
d = []
T = [[0] * (2 * K) for i in range(2 * K)]
for i in range(N):
    x, y, c = input().split()
    x, y = int(x) % (2 * K), int(y) % (2 * K)
    if c == 'W':
        y = (y + K) % (2 * K)

    d.append((x, y))
    T[x][y] = 1

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

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

T.insert(0, [0] * (2 * K))
for i in range(2 * K + 1):
    T[i].insert(0, 0)


def calc(a, b, k1, k2):
    c, d = a + k1 - 1, b + k2 - 1
    return T[c][d] - T[c][b - 1] - T[a - 1][d] + T[a - 1][b - 1]


num = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        d1 = calc(i, j, K, K) + calc(i + K, j + K, K - i + 1, K - j + 1) + calc(0, j + K, i, K - j + 1)
        d2 = calc(i + K, 0, K - i + 1, j) + calc(0, 0, i, j)
        num = max(d1 + d2, num)
        num = max(N - d1 - d2, num)

print(num)

Submission status: Wrong Answer

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

for _ in range(n):
	x, y, c = input().split()
	x, y = (int(x) - 1) % (2*k), (int(y) - 1) % (2*k)
	if (c == "B") ^ (y >= k):
		x = (x-k) % (2*k)
		
	y %= k

	if x < k:
		white[0][0] += 1
		white[x][0] += -1
		white[x+k][0] += -1
		white[2*k][0] += 1
		white[0][y] += -1
		white[x][y] += 2
		white[x+k][y] += -2
		white[2*k][y] += 1
		white[x][k] += -1
		white[x+k][k] += 1

	else:
		white[x-k][0] += 1
		white[x][0] += -1
		white[0][y] += 1
		white[x-k][y] += -2
		white[x][y] += 2
		white[2*k][y] += -1
		white[0][k] += -1
		white[x-k][k] += 1
		white[x][k] += -1
		white[2*k][k] += 1

#print(white)

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

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

#print(white)

ans = 0
for i in range(2*k):
	for j in range(k):
		ans = max(ans, white[i][j])

print(ans)

Submission status: Wrong Answer

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

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

	if x < k:
		white[0][0] += 1
		white[x][0] += -1
		white[x+k][0] += -1
		white[2*k][0] += 1
		white[0][y] += -1
		white[x][y] += 2
		white[x+k][y] += -2
		white[2*k][y] += 1
		white[x][k] += -1
		white[x+k][k] += 1

	else:
		white[x-k][0] += 1
		white[x][0] += -1
		white[0][y] += 1
		white[x-k][y] += -2
		white[x][y] += 2
		white[2*k][y] += -1
		white[0][k] += -1
		white[x-k][k] += 1
		white[x][k] += -1
		white[2*k][k] += 1

#print(white)

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

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

#print(white)

ans = 0
for i in range(2*k):
	for j in range(k):
		ans = max(ans, white[i][j])

print(ans)

Submission status: Wrong Answer

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

MeetDemand =[[0 for y in range(dK+1)] for x in range(K+1)]
for i in range(N):
    x, y, c =input().split()
    x = int(x) % dK
    y = (int(y)+K if c=="W" else int(y)) % dK
    if K <= x:
        if 0 <= y < K:
            x -= K
            y += K
        else:
            x %= K
            y %= K
    if 0 <= y < K:
        MeetDemand[0][0] += 1
        MeetDemand[x+1][y+1] += 2
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][0] -= 1
        MeetDemand[0][y+K+1] += 1
        MeetDemand[x+1][y+K+1] -= 2
    else:
        MeetDemand[0][y-K+1] += 1
        MeetDemand[x+1][y-K+1] -= 2
        MeetDemand[x+1][0] += 1
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][y+1] += 2

for x in range(K):
    MeetDemand[x][dK] = 0
    for y in range(1, dK):
        MeetDemand[x][y] += MeetDemand[x][y-1]
for y in range(dK):
    MeetDemand[K][y] = 0
    for x in range(1, K):
        MeetDemand[x][y] += MeetDemand[x-1][y]

Ans = max(max(MeetDemand))
print(Ans)

Submission status: Wrong Answer

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

MeetDemand =[[0 for c in range(dK+1)] for r in range(dK)]
for i in range(N):
    x, y, c =input().split()
    x = int(x)
    y = int(y)
    if c == "W":
        y += K
    x %= dK
    y %= dK
    if 0 <= x < K and 0 <= y < K:
        MeetDemand[0][0] += 1
        MeetDemand[x+1][y+1] += 2
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][0] -= 1
        MeetDemand[x][y+K+1] += 1
        MeetDemand[x+1][y+K+1] -= 2
    elif 0 <= x < K:
        MeetDemand[0][y-K+1] += 1
        MeetDemand[x+1][y-K+1] -= 2
        MeetDemand[x+1][0] += 1
        MeetDemand[x][y+1] -= 1
        MeetDemand[x+1][y+1] += 2
    elif 0 <= y < K:
        MeetDemand[x-K+1][0] += 1
        MeetDemand[x-K+1][y+1] -= 2
        MeetDemand[0][y+1] += 1
        MeetDemand[0][y+K+1] -= 1
        MeetDemand[x-K+1][y+K+1] += 2
    else:
        MeetDemand[0][0] += 1
        MeetDemand[0][y-K+1] -= 1
        MeetDemand[x-K+1][0] -= 1
        MeetDemand[x-K+1][y-K+1] += 2
        MeetDemand[0][y+1] += 1
        MeetDemand[x-K+1][y+1] -= 2

for x in range(K+1):
    for y in range(1, dK+1):
        MeetDemand[x][y] += MeetDemand[x][y-1]
Ans = max(MeetDemand[0][:dK+1])
for y in range(dK+1):
    for x in range(1, K+1):
        MeetDemand[x][y] += MeetDemand[x-1][y]
        Ans = max(Ans, MeetDemand[x][y])
print(Ans)

Submission status: Wrong Answer

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

MeetDemand =[[0 for c in range(dK)] for r in range(dK)]
for i in range(N):
    x, y, c =input().split()
    x = int(x)
    y = int(y)
    if c == "W":
        y += K
    x %= dK
    y %= dK
    if 0 <= x < K and 0 <= y < K:
        MeetDemand[0][0] += 1
        MeetDemand[x+1][y+1] += 2
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][0] -= 1
    elif 0 <= x < K:
        MeetDemand[0][y-K+1] += 1
        MeetDemand[x+1][y-K+1] -= 2
        MeetDemand[x+1][0] += 1
    elif 0 <= y < K:
        MeetDemand[x-K+1][0] += 1
        MeetDemand[x-K+1][y+1] -= 2
        MeetDemand[0][y+1] += 1
    else:
        MeetDemand[0][0] += 1
        MeetDemand[0][y-K+1] -= 1
        MeetDemand[x-K+1][0] -= 1
        MeetDemand[x-K+1][y-K+1] += 2

for x in range(K+1):
    for y in range(1, K+1):
        MeetDemand[x][y] += MeetDemand[x][y-1]
Ans = max(MeetDemand[0][:K+1])
for y in range(K+1):
    for x in range(1, K+1):
        MeetDemand[x][y] += MeetDemand[x-1][y]
        Ans = max(Ans, MeetDemand[x][y])
print(Ans)

Submission status: Wrong Answer

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

MeetDemand =[[0 for c in range(dK)] for r in range(dK)]
for i in range(N):
    x, y, c =input().split()
    x = int(x)
    y = int(y)
    if c == "W":
        y += K
    x %= dK
    y %= dK
    if 0 <= x < K and 0 <= y < K:
        MeetDemand[0][0] += 1
        MeetDemand[x+1][y+1] += 2
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][0] -= 1
    elif 0 <= x < K:
        MeetDemand[0][y-K+1] += 1
        MeetDemand[x+1][y-K+1] -= 2
        MeetDemand[x+1][0] += 1
    elif 0 <= y < K:
        MeetDemand[x-K+1][0] += 1
        MeetDemand[x-K+1][y+1] -= 2
        MeetDemand[0][y+1] += 1
    else:
        MeetDemand[0][0] += 1
        MeetDemand[0][y-K+1] -= 1
        MeetDemand[x-K+1][0] -= 1
        MeetDemand[x-K+1][y-K+1] += 2

for x in range(K+1):
    for y in range(1, K+1):
        MeetDemand[x][y] += MeetDemand[x][y-1]
Ans = MeetDemand[0][0]
for y in range(K+1):
    for x in range(1, K+1):
        MeetDemand[x][y] += MeetDemand[x-1][y]
        Ans = max(Ans, MeetDemand[x][y])
print(Ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
dpw = [[0]*(4*k+1) for i in range(4*k+1)]
for i in range(n):
  x,y,c = map(str,input().split())
  x = int(x)
  y = int(y)
  if c == "W":
    dpw[x%(2*k)+1][y%(2*k)+1] += 1
    dpw[x%(2*k)+2*k+1][y%(2*k)+2*k+1] += 1
    dpw[x%(2*k)+2*k+1][y%(2*k)+1] += 1
    dpw[x%(2*k)+1][y%(2*k)+2*k+1] += 1
  else:
    y+=k
    dpw[x%(2*k)+1][y%(2*k)+1] += 1
    dpw[x%(2*k)+2*k+1][y%(2*k)+2*k+1] += 1
    dpw[x%(2*k)+2*k+1][y%(2*k)+1] += 1
    dpw[x%(2*k)+1][y%(2*k)+2*k+1] += 1
for i in range(1,4*k+1):
  for j in range(1,4*k+1):
    dpw[i][j] += dpw[i-1][j] + dpw[i][j-1]-dpw[i-1][j-1]
ans = 0
for i in range(1,2*k+1):
  for j in range(1,2*k+1):
    tmp = 0
    tmp += dpw[k+i-1][k+j-1]+dpw[i-1][j-1]-dpw[i-1][j+k-1]-dpw[i+k-1][j-1]
    tmp += dpw[k+i-1+k][k+j-1+k]+dpw[i-1+k][j-1+k]-dpw[i-1+k][j+k-1+k]-dpw[i+k-1+k][j-1+k]
    tmp += dpw[k+i-1+k][k+j-1]+dpw[i-1+k][j-1]-dpw[i-1+k][j+k-1]-dpw[i+k-1+k][j-1]
    tmp += dpw[k+i-1][k+j-1+k]+dpw[i-1][j-1+k]-dpw[i-1][j+k-1+k]-dpw[i+k-1][j-1+k]
    ans = max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
from numpy import*
N,K=map(int,input().split())
m=zeros((3*K,3*K),dtype=int)
L=2*K
o=0
for _ in [0]*N:
 x,y,c=input().split()
 x,y=int(x)%L,int(y)%L
 t=c=='W'
 m[x,y]+=2*t-1
 o+=t
for _ in [0,0]:
 m[L:]=m[:K]
 m=cumsum(m,axis=0)
 m[:L]-=m[K:]
 m=m.T
m=m[:L,:L]
print(o+int((m+roll(roll(m,K,axis=0),K,axis=1)).max()))

Submission status: Wrong Answer

Solution code:
from numpy import*
N,K=map(int,input().split())
m=zeros((3*K,3*K))
L=2*K
o=0
for _ in [0]*N:
 x,y,c=input().split()
 x,y=int(x)%L,int(y)%L
 t=c=='W'
 m[x,y]+=2*t-1
 o+=t
for _ in [0,0]:
 m[L:]=m[:K]
 m=cumsum(m,axis=0)
 t=m[K:]
 m[:L]-=t
 m=m.T
m=m[:L,:L]
print(o+int((m+roll(roll(m,K,axis=0),K,axis=1)).max()))

Submission status: Wrong Answer

Solution code:
from numpy import*
N,K=map(int,input().split())
m=zeros((3*K,3*K))
L=2*K
o=0
for _ in [0]*N:
 x,y,c=input().split()
 x,y=int(x)%L,int(y)%L
 t=c=='W'
 m[x,y]+=2*t-1
 o+=t
for _ in [0,0]:
 m[L:]=m[:K]
 m=cumsum(m,axis=0)
 m[:L]-=m[K:]
 m=m.T
m=m[:L,:L]
print(o+int((m+roll(roll(m,K,axis=0),K,axis=1)).max()))