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: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
favor = [tuple(input().split()) for _ in range(n)]
square = [[0 for _ in range(k)] for _ in range(k)]
initscore = 0
for xc, yc, c in favor:
    x = int(xc)
    y = int(yc)
    x %= 2*k
    y %= 2*k
    if (x in range(k) and y in range(k)) or (x in range(k, 2*k) and y in range(k, 2*k)):
        if c == 'B':
            square[x%k][y%k] += 1
        else:
            square[x%k][y%k] -= 1
            initscore += 1
    else:
        if c == 'B':
            square[x%k][y%k] -= 1
            initscore += 1
        else:
            square[x%k][y%k] += 1
cum = [[0 for _ in range(k+1)] for _ in range(k+1)]
for i in range(k):
    for j in range(k):
        cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + square[i][j]
maxscore = 0
for i in range(k):
    for j in range(k):
        score1 = 2*cum[i][j] + cum[k][k] - cum[i][k] - cum[k][j]
        score2 = cum[k][k] - score1
        maxscore = max(maxscore, initscore + max(score1, score2))
print(maxscore)

Submission status: Time Limit Exceeded

Solution code:
N,K = list(map(int,input().split()))
wh_sum =[[0 for j in range(4*K)] for i in range(4*K)]
bl_sum =[[0 for j in range(4*K)] for i in range(4*K)]

def get_imos(imos,x_1,y_1,x_2,y_2):
    
    sq_1 = imos[x_2][y_2]
    sq_2 = 0
    sq_3 = 0
    sq_4 = 0
    if x_1 > 0:
        sq_2 = imos[x_1-1][y_2]
    if y_1 > 0:
        sq_3 = imos[x_2][y_1-1]
    if x_1 > 0 and y_1 > 0:
        sq_4 = imos[x_1-1][y_1-1]

    return sq_1 - sq_2 - sq_3 + sq_4
        

ans = 0   
    

def pr(s):
    for i in s:
        print (i)


for i in range(N):
    x,y,c = list(input().split())
    x = int(x)
    y = int(y)
    if c == 'W':
        wh_sum[x%(2*K)][y%(2*K)] += 1
        
    else:
        bl_sum[x%(2*K)][y%(2*K)] += 1

for x in range(4*K):
    for y in range(4*K):
        wh_sum[x][y]= wh_sum[x%(2*K)][y%(2*K)] 
        bl_sum[x][y]= bl_sum[x%(2*K)][y%(2*K)]

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


for x in range(2*K):
    for y in range(2*K):
        w = get_imos(wh_sum,x,y,x+K-1,y+K-1)+get_imos(wh_sum,x+K,y+K,x+2*K-1,y+2*K-1)
        b = get_imos(bl_sum,x,y+K,x+K-1,y+2*K-1)+get_imos(bl_sum,x+K,y,x+2*K-1,y+K-1)
        ans = max(ans,w+b)
        

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int, input().split())
mod = 2*K
field = np.zeros((2*K+1, 2*K+1), dtype='i')


def gen_pattern(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 = input().split()
    x, y = int(x), int(y)
    if c == 'W':
        y += K
    x %= mod
    y %= mod
    for tmp in [0, K]:
        for l, r in gen_pattern((x+tmp) % mod):
            for b, t in gen_pattern((y+tmp) % mod):
                field[l][b] += 1
                field[l][t] -= 1
                field[r][b] -= 1
                field[r][t] += 1

print(field.cumsum(axis=0).cumsum(axis=1).max())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int, input().split())
mod = 2*K
field = np.zeros((2*K+1, 2*K+1), dtype='i')


def gen_pattern(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 = input().split()
    x, y = int(x), int(y)
    if c == 'W':
        y += K
    x %= mod
    y %= mod
    for tmp in [0, K]:
        for l, r in gen_pattern((x+tmp) % mod):
            for b, t in gen_pattern((y+tmp) % mod):
                field[l][b] += 1
                field[l][t] -= 1
                field[r][b] -= 1
                field[r][t] += 1

ans = np.max(np.cumsum(np.cumsum(field, axis=0), axis=1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

def main():
    na = list(map(int, input().split()))
    N = na[0]
    K = na[1]
    x = []
    y = []
    c = []
    for i in range(N):
        sa = input().split()
        x.append(int(sa[0]))
        y.append(int(sa[1]))
        c.append(True if sa[2] == 'W' else False)

    hopes = [[0 for j in range(K * 2)] for i in range(K * 3)]
    xsum = [0 for j in range(K * 2)]
    ysum = [[0 for j in range(K * 2)] for i in range(K * 3)]

    for i in range(N):
        if c[i]:
            x[i] += K
        xmod = x[i] % (K * 2)
        ymod = y[i] % (K * 2)
        if K <= xmod and K <= ymod:
            xmod -= K
            ymod -= K
        elif K <= ymod:
            xmod += K
            ymod -= K

        hopes[xmod][ymod] += 1
        if xmod < K:
            hopes[xmod + K][ymod + K] += 1
            hopes[xmod + K * 2][ymod] += 1
        else:
            hopes[xmod - K][ymod + K] += 1
            hopes[xmod + K][ymod + K] += 1

    for j in range(K * 2):
        for i in range(K):
            xsum[j] += hopes[i][j]
    for i in range(K):
        ysum[i][0] = ysum[i + K * 2][0] = s = sum(hopes[i][:K])
        for j in range(1, K):
            s += (hopes[i][j + K - 1] - hopes[i][j - 1])
            ysum[i][j] = ysum[i + K * 2][j] = s
    for i in range(K, K * 2):
        ysum[i][0] = s = sum(hopes[i][:K])
        for j in range(1, K):
            s += (hopes[i][j + K - 1] - hopes[i][j - 1])
            ysum[i][j] = s

    h0 = []
    hmax = h = sum(xsum[:K])
    h0.append(h)
    for j in range(1, K):
        h += (xsum[j + K - 1] - xsum[j - 1])
        hmax = max(hmax, h)
        h0.append(h)
    for j in range(K):
        h = h0[j]
        for i in range(1, K * 2):
            h += (ysum[i + K - 1][j] - ysum[i - 1][j])
            hmax = max(hmax, h)

    print(hmax)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K = list(map(int,input().split()))
d = []
for n in range(N):
    dd = input().split()
    x = int(dd[0])%(K)
    y = int(dd[1])%(K)
    c = dd[2]
    if (int(dd[0])//K+int(dd[1])//K) % 2 == 1:
        if c == "W":
            c = "B"
        else:
            c = "W"

    d.append([x,y,c])

def color(x,y,offsetX,offsetY,k):
    if ((x+offsetX)//k + (y+offsetY)//k) % 2 == 0:
        return "B"
    return "W"

def check(offsetX,offsetY,k):
    count = 0
    count_inverse = 0
    for a in d:
        r = color(a[0],a[1],offsetX,offsetY,k)
        if r == a[2]:
            count += 1
    return max(count,len(d)-count)

s = []
for i in range(K):
    for j in range(K):
        r = check(i,j,K)
        #print(i,j,r)
        s.append(r)

print(max(s))

Submission status: Time Limit Exceeded

Solution code:
N,K = list(map(int,input().split()))
d = []
for n in range(N):
    dd = input().split()
    d.append([int(dd[0]),int(dd[1]),dd[2]])

def color(x,y,offsetX,offsetY,k):
    if ((x+offsetX)//k + (y+offsetY)//k) % 2 == 0:
        return "B"
    return "W"

def check(offsetX,offsetY,k):
    count = 0
    for a in d:
        r = color(a[0],a[1],offsetX,offsetY,k)
        if r == a[2]:
            count += 1
    return count

s = []
for i in range(K*2):
    for j in range(K*2):
        r = check(i,j,K)
        #print(i,j,r)
        s.append(r)

print(max(s))

Submission status: Time Limit Exceeded

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

black = 0
imos = [[0 for i in range(k)] for j in range(k)]

for i in range(n):
    X, Y, C = input().split()
    x = int(X)
    y = int(Y)
    c = 1 if C == "W" else 0

    x = x % (2*k)
    y = y % (2*k)
    if x > k-1:
        x -= k
        c += 1
    if y > k-1:
        y -= k
        c += 1
    c = 1 if c%2 == 1 else -1
    imos[x][y] += c
    if c == -1:
        black += 1

for i in range(k):
    for j in range(k-1):
        imos[i][j+1] += imos[i][j]

for j in range(k):
    for i in range(k-1):
        imos[i+1][j] += imos[i][j]

ans = 0
for i in range(k):
    for j in range(k):
        m = imos[k-1][k-1] - imos[k-1][j] - imos[i][k-1] + 2 * imos[i][j]
        ans = max(ans, max(n-(black+m), black+m))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
XYC=[list(input().split()) for i in range(N)]

MAP=[[0 for i in range(K*2+1)] for j in range(K*2+1)]
mod=K*2
for x,y,c in XYC:
    x=int(x)
    y=int(y)
    if c=="W":
        x+=K

    MAP[x%mod+1][y%mod+1]+=1
    MAP[(x+K)%mod+1][(y+K)%mod+1]+=1




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

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

ANS=0
for i in range(K):
    for j in range(K):

        if ANS<MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j]:
            ANS=MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j]
        if ANS<N-(MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j]):
            ANS=N-(MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j])
print(ANS)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, k = list(map(int, input().split()))

def get_bound(x):
    if x < k-1:
        return [(0, x+1), (x+k+1, 2*k)]
    else:
        return [(x-k+1, x+1)]

blacks = np.zeros((2*k+1, 2*k+1))
for _ in range(n):
    x, y, c = input().split()
    x = int(x)%(2*k)
    y = int(y)%(2*k) if c == 'B' else (int(y)+k)%(2*k)

    for shift in [0, k]:
        for b, t in get_bound((y+shift)%(2*k)):
            for l, r in get_bound((x+shift)%(2*k)):
                blacks[b, l] += 1
                blacks[t, l] -= 1
                blacks[b, r] -= 1
                blacks[t, r] += 1
        
ans = np.max(np.cumsum(np.cumsum(blacks, axis = 1), axis = 0))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np

s_in = lambda: stdin.readline()[:-1] # s = s_in()
d_in = lambda: int(stdin.readline()) # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split())) # List = ds_in()

N, K = ds_in()
checker1 = np.zeros((K+1, K+1))
checker2 = np.zeros((K+1, K+1))

for _ in range(N):
    x, y, c = s_in().split()
    x = int(x)
    y = int(y)
    c = 0 if c == 'W' else 1
    parity = ((x // K + y // K) % 2 + c) % 2
    if parity:
        checker2[x%K + 1, y%K + 1] += 1
    else:
        checker1[x%K + 1, y%K + 1] += 1

cum_1 = np.cumsum(np.cumsum(checker1, axis=0), axis=1)
cum_2 = np.cumsum(np.cumsum(checker2, axis=0), axis=1)

ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        cand = (cum_1[i-1, j-1] + cum_1[-1, -1] + cum_2[i-1, -1] + cum_2[-1, j-1])\
                - (cum_2[i-1, j-1] + cum_1[i-1, -1])\
                - (cum_2[i-1, j-1] + cum_1[-1, j-1])\
                + cum_1[i-1, j-1]
        ans = max(ans, cand, N-cand)

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))
xyc=[]
for i in range(N):
    tmp=list(input().split())
    tmp2=[]
    tmp2.append(int(tmp[0]))
    tmp2.append(int(tmp[1]))
    if tmp[2]=='W':
        tmp2.append(0)
    else:
        tmp2.append(1)
    xyc.append(tmp2)

ans=[]

for i in range(K):
    for j in range(2*K):
        a=[]
        for row in xyc:
            x=row[0]+i
            y=row[1]+j
            if (x//K+y//K)%2==row[2]:
                a.append(1)

        ans.append(sum(a))

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, XYC):
    ans = []
    for i in range(K):
        for j in range(K):
            # print(i, j)
            a_w = 0
            a_b = 0
            for x, y, c in XYC:
                x_ = ((x+j) // K) % 2
                y_ = ((y+i) // K) % 2
                if (x_ + y_) % 2 == 0:
                    if c == 'W':
                        a_w += 1
                    else:
                        a_b += 1
                else:
                    if c == 'B':
                        a_w += 1
                    else:
                        a_b += 1
            ans.append(a_w)
            ans.append(a_b)
            # print(ans[-2])
            # print(ans[-1])
    return max(ans)


def main():
    N, K = read_int_n()
    XYC = [read_str_n() for _ in range(N)]
    XYC = list(map(lambda x: (int(x[0]), int(x[1]), x[2]), XYC))
    print(slv(N, K, XYC))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
mp1 = [[0] * k for _ in range(k)]
mp2 = [[0] * k for _ in range(k)]
for _ in range(n):
  x, y, c = input().split()
  t = int(x) // k + int(y) // k
  x = int(x) % k
  y = int(y) % k
  if c == "B":
    t += 1
  if t % 2:
    mp1[y][x] += 1
  else:
    mp2[y][x] += 1

for x in range(1, k):
  mp1[0][x] += mp1[0][x - 1]
  mp2[0][x] += mp2[0][x - 1]

for y in range(1, k):
  acc1 = 0
  acc2 = 0
  for x in range(k):
    acc1 += mp1[y][x]
    mp1[y][x] = acc1 + mp1[y - 1][x]
    acc2 += mp2[y][x]
    mp2[y][x] = acc2 + mp2[y - 1][x]

ans = 0
sum1 = mp1[k - 1][k - 1]
sum2 = mp2[k - 1][k - 1]
mp1k = mp1[k - 1]
mp2k = mp2[k - 1]
for y in range(k):
  mp1y = mp1[y]
  mp1yk = mp1y[k - 1]
  mp2y = mp2[y]
  mp2yk = mp2y[k - 1]
  for x in range(k):
    mp1yx = mp1y[x]
    mp2yx = mp2y[x]
    mp1kx = mp1k[x]
    mp2kx = mp2k[x]

    ans = max(ans, 2 * mp1yx + sum1 - mp1yk - mp1kx + mp2kx + mp2yk - 2 * mp2yx)
    ans = max(ans, 2 * mp2yx + sum2 - mp2yk - mp2kx + mp1kx + mp1yk - 2 * mp1yx)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
v = []
for i in range(n):
    abc = [x for x in input().split()]
    a = int(abc[0])
    b = int(abc[1])
    c = abc[2]
    if c == 'W':
        b += k
    v.append((a % (2*k), b % (2*k)))

s = [[0 for _ in range(6*k+1)] for _ in range(6*k+1)]
s2 = [[0 for _ in range(k+1)] for _ in range(k+1)]
s3 = [[0 for _ in range(k+1)] for _ in range(k+1)]

for i in range(n):
    s[v[i][1]][v[i][0]] += 1
    s[v[i][1]+k][v[i][0]+k] += 1
    s[v[i][1]+k][v[i][0]] -= 1
    s[v[i][1]][v[i][0]+k] -= 1

for i in range(3*k):
    for j in range(3*k):
        s[i+1][j] += s[i][j]
for i in range(3*k):
    for j in range(3*k):
        s[i][j+1] += s[i][j]

for i in range(3*k):
    for j in range(3*k):
        c = (i//k+j//k) % 2
        if c == 0:
            s2[i % k][j % k] += s[i][j]
        else:
            s3[i % k][j % k] += s[i][j]
res = 0

for i in range(k):
    for j in range(k):
        res = max(res, s2[i][j])
        res = max(res, s3[i][j])
print(res)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
v = []
for i in range(n):
    abc = [x for x in input().split()]
    a = int(abc[0])
    b = int(abc[1])
    c = abc[2]
    if c == 'W':
        b += k
    v.append((a % (2*k), b % (2*k)))
    
s = [[0 for _ in range(6*k+1)] for _ in range(6*k+1)]
s2 = [[0 for _ in range(k+1)] for _ in range(k+1)]
s3 = [[0 for _ in range(k+1)] for _ in range(k+1)]

for i in range(n):
    s[v[i][1]][v[i][0]] += 1
    s[v[i][1]+k][v[i][0]+k] += 1
    s[v[i][1]+k][v[i][0]] -= 1
    s[v[i][1]][v[i][0]+k] -= 1

for i in range(3*k):
    for j in range(3*k):
        s[i+1][j] += s[i][j]
for i in range(3*k):
    for j in range(3*k):
        s[i][j+1] += s[i][j]

for i in range(3*k):
    for j in range(3*k):
        c = (i//k+j//k) % 2
        if c == 0:
            s2[i % k][j % k] += s[i][j]
        else:
            s3[i % k][j % k] += s[i][j]

            res = 0
for i in range(k):
    for j in range(k):
        res = max(res, s2[i][j])
        res = max(res, s3[i][j])
print(res)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
xs , ys , cs = [], [], []
for i in range(n):
  tmp = input().split()
  xs.append(int(tmp[0])%(k*2))
  ys.append(int(tmp[1])%(k*2))
  cs.append(tmp[2] == "B")
for i in range(n):
  if xs[i] >= k:
    xs[i] = (xs[i] + k) % (k*2)
    cs[i] = not cs[i]
  if ys[i] >= k:
    ys[i] = (ys[i] + k) % (k*2)
    cs[i] = not cs[i]
ans = 0
for i in range(k):
  for j in range(k):
    count = 0
    for m in range(n):
      if (xs[m]>=i and ys[m]>=j) or (xs[m]<i and ys[m]<j):
        count += int(cs[m])
      else:
        count += int(not(cs[m]))
    t = max(count,n-count)
    if t > ans:
      ans = t
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
xs , ys , cs = [], [], []
for i in range(n):
  tmp = input().split()
  xs.append(int(tmp[0])%(k*2))
  ys.append(int(tmp[1])%(k*2))
  cs.append(tmp[2] == "B")
for i in range(n):
  if xs[i] >= k:
    xs[i] = (xs[i] + k) % (k*2)
    cs[i] = not cs[i]
  if ys[i] >= k:
    ys[i] = (ys[i] + k) % (k*2)
    cs[i] = not cs[i]
ans = 0
for i in range(k):
  for j in range(k):
    count = 0
    for m in range(n):
      if (xs[m]>=i and ys[m]>=j) or (xs[m]<i and ys[m]<j):
        count += int(cs[m])
      else:
        count += int(not(cs[m]))
    if count > ans:
      ans = count
for i in range(k):
  for j in range(k):
    count = 0
    for m in range(n):
      if (xs[m]>=i and ys[m]>=j) or (xs[m]<i and ys[m]<j):
        count += int(not(cs[m]))
      else:
        count += int(cs[m])
    if count > ans:
      ans = count
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Desire:
	def __init__(self, x, y, c):
		# c for color
		self.x = x
		self.y = y
		self.c = c

class Check:
	def __init__(self, k, c):
		self.k = k
		self.c = c
		self.desires = []

	def add_desire(self, desire):
		self.desires.append(desire)

	def get_max(self):
		_max = 0
		for i in range(self.k+1):
			for j in range(self.k+1):
				count = 0
				for desire in self.desires:
					if (desire.x >= i and desire.y >= j) or (desire.x < i and desire.y < j):
						count += 1 if desire.c == self.c else 0

					if (desire.x >= i and desire.y < j) or (desire.x < i and desire.y >= j):
						count += 1 if desire.c != self.c else 0

				_max = count if count > _max else _max

		return _max


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

checkW = Check(k, "W")

for i in range(n):
	x, y, c = input().split()
	x = int(x)
	y = int(y)

	x = -1*x+k-1 if x<0 else x
	y = -1*y+k-1 if y<0 else y
	
	bigX = x//k
	bigY = y//k

	localX = x%k
	localY = y%k
	localC = c

	if (bigX + bigY) % 2 != 0:
		localC = "W" if localC == "B" else "B"
		
	desire = Desire(localX, localY, localC)
	checkW.add_desire(desire)

print(checkW.get_max())

Submission status: Time Limit Exceeded

Solution code:
def imos2d(x1, y1, x2, y2, board):
    board[y1][x1] += 1
    board[y2][x2] += 1
    board[y2][x1] -= 1
    board[y1][x2] -= 1


if __name__ == '__main__':
    N, K = map(int, input().split())
    lines = [input() for _ in range(N)]

    # N, K = 4, 3
    # lines = ["0 1 W", "1 2 W", "5 3 B", "5 4 B"]

    K2 = 2 * K
    add_dict = {"W": 0, "B": K}
    board = [[0 for _ in range(K2 + 1)] for _ in range(K2 + 1)]
    for line in lines:
        ls = line.split()
        x = int(ls[0]) % K2
        y = (int(ls[1]) + add_dict[ls[2]]) % K2

        if (x < K and y < K) or (K <= x and K <= y):
            # 左上・右上・中央・左下・右下

            x_ = x % K
            y_ = y % K

            # 左上
            imos2d(0, 0, x_ + 1, y_ + 1, board)
            # 右上
            imos2d(x_ + K + 1, 0, K2, y_ + 1, board)
            # 左下
            imos2d(0, y_ + K + 1, x_ + 1, K2, board)
            # 右下
            imos2d(x_ + K + 1, y_ + K + 1, K2, K2, board)
            # 中央
            imos2d(x_ + 1, y_ + 1, x_ + K + 1, y_ + K + 1, board)
        else:
            # 上・下・左・右
            x_ = x % K
            y_ = y % K

            # 上
            imos2d(x_ + 1, 0, x_ + K + 1, y_ + 1, board)
            # 下
            imos2d(x_ + 1, y_ + K + 1, x_ + K + 1, K2, board)

            # 左
            imos2d(0, y_ + 1, x_ + 1, y_ + K + 1, board)
            imos2d(x_ + K + 1, y_ + 1, K2, y_ + K + 1, board)

    for y in range(K2):
        for x in range(K2):
            board[y][x + 1] += board[y][x]

    for y in range(K2):
        for x in range(K2):
            board[y + 1][x] += board[y][x]

    answer = 0
    for y in range(K2 + 1):
        for x in range(K2 + 1):
            answer = max(answer, board[y][x])

    print(answer)

Submission status: Time Limit Exceeded

Solution code:
def imos2d(x1, y1, x2, y2, board):
    board[y1][x1] += 1
    board[y2][x2] += 1
    board[y2][x1] -= 1
    board[y1][x2] -= 1


if __name__ == '__main__':
    N, K = map(int, input().split())
    lines = [input() for _ in range(N)]

    # N, K = 4, 3
    # lines = ["0 1 W", "1 2 W", "5 3 B", "5 4 B"]

    K2 = 2 * K
    add_dict = {"W": 0, "B": K}
    board = [[0 for _ in range(K2 + 1)] for _ in range(K2 + 1)]
    for line in lines:
        ls = line.split()
        x = int(ls[0]) % K2
        y = (int(ls[1]) + add_dict[ls[2]]) % K2

        if (x < K and y < K) or (K <= x and K <= y):
            # 左上・右上・中央・左下・右下

            x_ = x % K
            y_ = y % K

            # 左上
            imos2d(0, 0, x_ + 1, y_ + 1, board)
            # 右上
            imos2d(x_ + K + 1, 0, K2, y_ + 1, board)
            # 左下
            imos2d(0, y_ + K + 1, x_ + 1, K2, board)
            # 右下
            imos2d(x_ + K + 1, y_ + K + 1, K2, K2, board)
            # 中央
            imos2d(x_ + 1, y_ + 1, x_ + K + 1, y_ + K + 1, board)
        else:
            # 上・下・左・右
            x_ = x % K
            y_ = y % K

            # 上
            imos2d(x_ + 1, 0, x_ + K + 1, y_ + 1, board)
            # 下
            imos2d(x_ + 1, y_ + K + 1, x_ + K + 1, K2, board)

            # 左
            imos2d(0, y_ + 1, x_ + 1, y_ + K + 1, board)
            imos2d(x_ + K + 1, y_ + 1, K2, y_ + K + 1, board)

    answer = 0
    for y in range(K2):
        for x in range(K2):
            board[y][x + 1] += board[y][x]
            answer = max(answer, board[y][x + 1])

    for y in range(K2):
        for x in range(K2):
            board[y + 1][x] += board[y][x]
            answer = max(answer, board[y + 1][x])

    print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def imos2d(x1, y1, x2, y2, board):
    board[y1][x1] += 1
    board[y2][x2] += 1
    board[y2][x1] -= 1
    board[y1][x2] -= 1


if __name__ == '__main__':
    N, K = map(int, input().split())
    lines = [input().split() for _ in range(N)]
    xs, ys, cs = zip(*[[int(line[0]), int(line[1]), line[2]] for line in lines])

    # N, K = 4, 3
    # xs = [0, 1, 5, 5]
    # ys = [1, 2, 3, 4]
    # cs = ["W", "W", "B", "B"]

    K2 = 2 * K
    add_dict = {"W": 0, "B": K}
    board = np.zeros((K2 + 1, K2 + 1), np.int64)
    for x, y, c in zip(xs, ys, cs):
        x = x % K2
        y = (y + add_dict[c]) % K2

        if (x < K and y < K) or (K <= x and K <= y):
            # 左上・右上・中央・左下・右下

            x_ = x % K
            y_ = y % K

            # 左上
            imos2d(0, 0, x_ + 1, y_ + 1, board)
            # 右上
            imos2d(x_ + K + 1, 0, K2, y_ + 1, board)
            # 左下
            imos2d(0, y_ + K + 1, x_ + 1, K2, board)
            # 右下
            imos2d(x_ + K + 1, y_ + K + 1, K2, K2, board)
            # 中央
            imos2d(x_ + 1, y_ + 1, x_ + K + 1, y_ + K + 1, board)
        else:
            # 上・下・左・右
            x_ = x % K
            y_ = y % K

            # 上
            imos2d(x_ + 1, 0, x_ + K + 1, y_ + 1, board)
            # 下
            imos2d(x_ + 1, y_ + K + 1, x_ + K + 1, K2, board)

            # 左
            imos2d(0, y_ + 1, x_ + 1, y_ + K + 1, board)
            imos2d(x_ + K + 1, y_ + 1, K2, y_ + K + 1, board)

    board_cum = board.cumsum(axis=0).cumsum(axis=1)
    print(board_cum.max())

Submission status: Time Limit Exceeded

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

score = [[0 for x in range(K+1)] for y in range(K+1)]
base_hope = 0

for i in range(N):
    x, y, c = input().split()
    x2, y2 = int(x) // K, int(y) // K
    x_coord, y_coord = int(x) % K + 1, int(y) % K + 1
    if ((x2 + y2) % 2 == 0 and c == "W") or ((x2 + y2) % 2 == 1 and c == "B"):
        score[y_coord][x_coord] += 1
        base_hope += 1
    else:
        score[y_coord][x_coord] -= 1

xy = [(x, y) for x in range(K) for y in range(K)]
for x, y in xy:
    score[y+1][x+1] += score[y+1][x] + score[y][x+1] - score[y][x]

max_hope = 0
for x, y in xy:
    hope = base_hope - score[K][x] - score[y][K] + 2 * score[y][x]
    true_hope = max(hope, N - hope)
    if true_hope > max_hope:
        max_hope = true_hope

print(max_hope)

Submission status: Time Limit Exceeded

Solution code:

N, K = map(int, input().split())

# スコア行列[K, K]
# 白チェッカー左下を(x, y)としたときの正解数-誤答数
score_matrix = [[0 for x in range(K+1)] for y in range(K+1)]
base_hope = 0

for i in range(N):
    x, y, c = input().split()
    x2, y2 = int(x) // K, int(y) // K
    x_coord, y_coord = int(x) % K, int(y) % K
    # 正解
    if ((x2 + y2) % 2 == 0 and c == "W") or ((x2 + y2) % 2 == 1 and c == "B"):
        score_matrix[y_coord+1][x_coord+1] += 1
        base_hope += 1
    # 誤答
    else:
        score_matrix[y_coord+1][x_coord+1] -= 1

# スコア行列の二次元累積和を求める O(K^2)
xy = [(x, y) for x in range(1, K+1) for y in range(1, K+1)]
for x, y in xy:
    score_matrix[y][x] += score_matrix[y][x-1] + score_matrix[y-1][x] - score_matrix[y-1][x-1]

# 希望行列を累積和に基づき計算していく O(K^2)
# 同時に最大値を計算
max_hope = 0
for x, y in xy:
    hope = base_hope - score_matrix[K][x-1] - score_matrix[y-1][K] + 2 * score_matrix[y-1][x-1]
    true_hope = max(hope, N - hope)
    if true_hope > max_hope:
        max_hope = true_hope

print(max_hope)

Submission status: Time Limit Exceeded

Solution code:

# 入力部
N, K = map(int, input().split())
data_list = []
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    data_list.append([x, y, c])

# スコア行列[K, K]
# 白チェッカー左下を(x, y)としたときの正解数-誤答数
score_matrix = [[0 for x in range(K)] for y in range(K)]

# 座標をmod Kに変換してスコア行列[K, K]を導出 O(N)
# 同時に初期値であるhope[0][0]も計算
score_matrix = [[0 for x in range(K)] for y in range(K)]
# 白チェッカー左下が(0, 0)のときの希望の数
base_hope = 0
for data in data_list:
    x, y, c = data[0] // K, data[1] // K, data[2]
    x_coord, y_coord = data[0] % K, data[1] % K
    # 正解
    if ((x + y) % 2 == 0 and c == "W") or ((x + y) % 2 == 1 and c == "B"):
        score_matrix[y_coord][x_coord] += 1
        base_hope += 1
    # 誤答
    else:
        score_matrix[y_coord][x_coord] -= 1
# print(score_matrix)

# スコア行列の二次元累積和を求める O(K^2)
xy = [(x, y) for x in range(K) for y in range(K)]
for x, y in xy:
    accum = score_matrix[y][x]
    if x > 0:
        accum += score_matrix[y][x-1]
    if y > 0:
        accum += score_matrix[y-1][x]
    if x > 0 and y > 0:
        accum -= score_matrix[y-1][x-1]
    score_matrix[y][x] = accum
# print(score_matrix)

# 希望行列を累積和に基づき計算していく O(K^2)
# 同時に最大値を計算
max_hope = 0
for x, y in xy:
    diff = 0
    if x > 0:
        diff += score_matrix[K-1][x-1]
    if y > 0:
        diff += score_matrix[y-1][K-1]
    if x > 0 and y > 0:
        diff -= 2 * score_matrix[y-1][x-1]
    hope = base_hope - diff
    true_hope = max(hope, N - hope)
    if true_hope > max_hope:
        max_hope = true_hope

print(max_hope)

Submission status: Time Limit Exceeded

Solution code:

# 入力部
N, K = map(int, input().split())
data_list = []
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    data_list.append([x, y, c])

# スコア行列[K, K]
# 白チェッカー左下を(x, y)としたときの正解数-誤答数
score_matrix = [[0 for x in range(K)] for y in range(K)]

# 座標をmod Kに変換してスコア行列[K, K]を導出 O(N)
# 同時に初期値であるhope[0][0]も計算
score_matrix = [[0 for x in range(K)] for y in range(K)]
# 白チェッカー左下が(0, 0)のときの希望の数
base_hope = 0
for data in data_list:
    x, y, c = data[0] // K, data[1] // K, data[2]
    x_coord, y_coord = data[0] % K, data[1] % K
    # 正解
    if ((x + y) % 2 == 0 and c == "W") or ((x + y) % 2 == 1 and c == "B"):
        score_matrix[y_coord][x_coord] += 1
        base_hope += 1
    # 誤答
    else:
        score_matrix[y_coord][x_coord] -= 1
# print(score_matrix)

# スコア行列の二次元累積和を求める O(K^2)
for y in range(K):
    for x in range(K):
        accum = score_matrix[y][x]
        if x > 0:
            accum += score_matrix[y][x-1]
        if y > 0:
            accum += score_matrix[y-1][x]
        if x > 0 and y > 0:
            accum -= score_matrix[y-1][x-1]
        score_matrix[y][x] = accum
# print(score_matrix)

# 希望行列を累積和に基づき計算していく O(K^2)
# 同時に最大値を計算
max_hope = 0
for y in range(K):
    for x in range(K):
        diff = 0
        if x > 0:
            diff += score_matrix[K-1][x-1]
        if y > 0:
            diff += score_matrix[y-1][K-1]
        if x > 0 and y > 0:
            diff -= 2 * score_matrix[y-1][x-1]
        hope = base_hope - diff
        true_hope = max(hope, N - hope)
        if true_hope > max_hope:
            max_hope = true_hope

print(max_hope)

Submission status: Time Limit Exceeded

Solution code:

def count_ans(w_start, K, info_list):
    ans = 0
    for x, y, c in info_list:
        ofs_x = w_start[0]
        ofs_y = w_start[1]
        x2 = (x - ofs_x) // K
        y2 = (y - ofs_y) // K
        if (x2 + y2) % 2 == 0:
            if c == "W":
                ans += 1
        else:
            if c == "B":
                ans += 1
    return ans


# 入力
N, K = map(int, input().split())
info_list = []
for i in range(N):
    tmp = input().split()
    tmp[0], tmp[1] = int(tmp[0]), int(tmp[1])
    info_list.append(tmp)

# 白チェッカーの左下位置リスト
w_start_list = [[x, y] for x in range(K) for y in range(K)]

current_max = 0
for w_start in w_start_list:
    # 合っている個数を数える
    ans = count_ans(w_start, K, info_list)
    ans = max(N - ans, ans)
    if current_max < ans:
        current_max = ans

print(current_max)