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:
import numpy as np

def prepare():
    for i in range(1,2*k+2):
        for j in range(1,2*k+2):
            X[i][j]=xy[i][j]+X[i-1][j]+X[i][j-1]-X[i-1][j-1]
def getsize(x1,y1,x2,y2):
    if x1>x2 or y1>y2:
        return 0
    else:
        return X[x2,y2]-X[x1-1,y2]-X[x2,y1-1]+X[x1-1,y1-1]




n,k=map(int,input().split())
xy=np.array([[0]*2011 for _ in range(2011)])
for _ in range(n):
    x,y,c=input().split()
    x,y=int(x),int(y)
    if c=='W':
        y+=k
    xy[x%(2*k)+1,y%(2*k)+1]+=1

X=np.array([[0]*2011 for _ in range(2011)])
prepare()

ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        tmp=getsize(1,1,i-1,j-1)+getsize(i,j,i+k-1,j+k-1)+getsize(i+k,j+k,2*k,2*k)+getsize(1,j+k,i-1,2*k)+getsize(i+k,1,2*k,j-1)
        ans=max(ans,max(tmp,n-tmp))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = raw_input().split(" ")
n = int(s[0])
k = int(s[1])

ts = []
for i in range(0, n):
 s = raw_input().split(" ")
 ts.append((int(s[0]), int(s[1]), s[2] == "B"))

maxSat = 0
for i in range(0, k):
 for j in range(0, k):
  sm = None
  for failures in range(0, n):
   sat = 0
   fails = 0
   for cp in range(0, n):
    c = ts[cp]
    x = c[0]
    y = c[1]
    if ((x-i)%(2*k) >= k) ^ ((y-j)%(2*k) >= k) ^ c[2]:
     sat += 1
    if sm == None:
     sm = ((x-i)%(2*k) >= k) ^ ((y-j)%(2*k) >= k) ^ c[2]
    if sm != ((x-i)%(2*k) >= k) ^ ((y-j)%(2*k) >= k) ^ c[2]:
     fails += 1
     if fails > failures:
      break
  maxSat = max(maxSat, sat, n - sat)
print maxSat

Submission status: Time Limit Exceeded

Solution code:
s = raw_input().split(" ")
n = int(s[0])
k = int(s[1])

ts = []
for i in range(0, n):
 s = raw_input().split(" ")
 ts.append((int(s[0]), int(s[1]), s[2] == "B"))

maxSat = 0
for i in range(0, k):
 for j in range(0, k):
  sm = None
  for failures in range(0, n):
   sat = 0
   fails = 0
   for cp in range(0, n):
    c = ts[cp]
    x = c[0]
    y = c[1]
    if ((x-i)%(2*k) >= k) ^ ((y-j)%(2*k) >= k) ^ c[2]:
     sat += 1
    else:
     fails += 1
     if fails > failures:
      break
  maxSat = max(maxSat, sat, n - sat)
print maxSat

Submission status: Time Limit Exceeded

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

MOD = 2*K

bdesires = [ [0]*MOD for _ in range(MOD) ]
wdesires = [ [0]*MOD for _ in range(MOD) ]

for _ in range(N):
    toks = input().split()
    x = int(toks[0])
    y = int(toks[1])
    c = toks[2]
    if c == 'B':
        bdesires[x%MOD][y%MOD] += 1
    else:
        wdesires[x%MOD][y%MOD] += 1

brows = [ [0]*MOD for _ in range(MOD) ]
bsquares = [ [0]*MOD for _ in range(MOD) ]
wrows = [ [0]*MOD for _ in range(MOD) ]
wsquares = [ [0]*MOD for _ in range(MOD) ]

color = [
        (bdesires, brows, bsquares),
        (wdesires, wrows, wsquares),
        ]
for desires, rows, squares in color:
    for i in range(MOD):
        rows[i][0] = sum(desires[i][0:K])

    for i in range(MOD):
        for j in range(1,MOD):
            rows[i][j] = rows[i][j-1] + desires[i][j-K-1] - desires[i][j-1]

    for j in range(MOD):
        squares[0][j] = sum([rows[i%MOD][j] for i in range(K) ])

    for i in range(1,MOD):
        for j in range(MOD):
            squares[i][j] = squares[i-1][j] + rows[i-K-1][j] - rows[i-1][j]

best = 0
for i in range(K):
    for j in range(K):
        best = max(
                best,
                bsquares[i][j]+bsquares[i+K][j+K]+wsquares[i+K][j]+wsquares[i][j+K],
                wsquares[i][j]+wsquares[i+K][j+K]+bsquares[i+K][j]+bsquares[i][j+K]
                )
print(best)

Submission status: Time Limit Exceeded

Solution code:
s = raw_input().split(" ")
n = int(s[0])
k = int(s[1])

ts = []
for i in range(0, n):
 s = raw_input().split(" ")
 ts.append((int(s[0]), int(s[1]), s[2] == "B"))

maxSat = 0
for i in range(0, k):
 for j in range(0, k):
  sm = None
  sat = 0
  for cp in range(0, n):
   c = ts[cp]
   x = c[0]
   y = c[1]
   if ((x-i)%(2*k) >= k) ^ ((y-j)%(2*k) >= k) ^ c[2]:
    sat += 1
  maxSat = max(maxSat, sat, n - sat)
print maxSat

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k = LI()
    aa = [LS() for _ in range(n)]
    a = [[int(_[0]) + (k if _[2] == 'W' else 0), int(_[1])] for _ in aa]
    k2 = k*2
    aa = [[0] * k2 for _ in range(k2)]
    dr = [0, -2, -1, 0, 1, 2, 1, 0, -1, 2, 2, -2, -2]
    dc = [0, 0, 1, 2, 1, 0, -1, -2, -1, 2, -2, 2, -2]

    for x,y in a:
        x %= k2
        y %= k2
        for i in range(13):
            cx = x + dr[i] * k
            cy = y + dc[i] * k
            if cx >= k2 or cy >= k2 or cx <= -k or cy <= -k:
                continue
            mx = max(cx, 0)
            my = max(cy, 0)
            aa[mx][my] += 1
            if cx < k:
                aa[cx+k][my] -= 1
                if cy < k:
                    aa[cx+k][cy+k] += 1
            if cy < k:
                aa[mx][cy+k] -= 1

    for i in range(k2):
        for j in range(1,k2):
            aa[i][j] += aa[i][j-1]
    for i in range(k2):
        for j in range(1,k2):
            aa[j][i] += aa[j-1][i]
    return max(max(c) for c in aa)


print(main())

Submission status: Time Limit Exceeded

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

max_count = 0
for i in range(2*K):
    for j in range(2*K):
        count = 0
        for d in dream:
            x = (int(d[0])+i) % (2*K)
            y = (int(d[1]) + j) % (2*K)
            c = d[2]

            pos_c = 'B'
            if (x >= K and y <K) or (x < K and y >= K):
                pos_c ='W'
            
            if c == pos_c:
                count += 1
        
        if count > max_count:
            max_count = count
        
        if max_count == K:
            break

print(max_count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

k = 0
l = 0
acc = None

def count_up(y1, x1, y2, x2):
    global acc, l
    if y1 > y2 or x1 > x2:
        return 0
    y2 += 1
    x2 += 1
    return  acc[y2][x2] - acc[y1][x2] - acc[y2][x1] + acc[y1][x1]

def main():
    global acc, k, l
    n, k = map(int, sys.stdin.readline().split())
    xycs = (map(lambda x: int(x) if x != 'B' and x != 'W' else x,
                 line.split()) for line in sys.stdin.readlines())

    l = k * 2
    yxs = (((y + k) % l, x % l) if c == 'W' else (y % l, x % l) for x, y, c in xycs)

    acc = [[0] * (l + 1) for _ in range(l + 1)]
    for y, x in yxs:
        acc[y + 1][x + 1] += 1
    for j in range(l):
        for i in range(l):
            acc[j + 1][i + 1] += acc[j + 1][i] + acc[j][i + 1] - acc[j][i]

    max_cnt = 0
    for j in range(k):
        for i in range(k):
            cnt = count_up(0, 0, j - 1, i - 1) + count_up(0, i + k, j - 1, l - 1) + count_up(j, i, j + k - 1, i + k - 1) + count_up(j + k, 0, l - 1, i - 1) + count_up(j + k, i + k, l - 1, l - 1)
            max_cnt = max(max_cnt, max(n - cnt, cnt))

    print(max_cnt)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k = list(map(int,input().split()))
k2 = 2*k
G = [None for i in range(n)]
max = 0
for i in range(n):
    x,y,c = list(input().split())
    x = int(x)
    y = int(y)
    G[i]=x,y,c

def dps():
    global max
    count = 0
    for a in range(k):
        for b in range(k):
            for i in range(n):
                x = (G[i][0]+a)%k2
                y = (G[i][1]+b)%k2
                c = G[i][2]
                if x < k and y < k:
                    if c == 'W':
                        count += 1
                if x < k and y >= k:
                    if c == 'B':
                        count += 1
                if x >= k and y < k:
                    if c == 'B':
                        count += 1
                if x >= k and y >= k:
                    if c == 'W':
                        count += 1
            if max < count:
                max = count
            if max < n-count:
                max = n-count
            count = 0

dps()
print(max)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import numpy as np

N, K = list(map(int, input().split()))
L = [list(map(str, input().split())) for _ in range(N)]

Ksq = K * 2
count = np.zeros((Ksq * Ksq), int)

for l in L:
    x = int(l[0]) % Ksq
    y = int(l[1]) % Ksq
    c = l[2]
    if (y < K and x >= K) or (y >= K and x < K):
        c = 'B' if c == 'W' else 'W'
    x %= K
    y %= K

    if c == 'W':
        i = 0
        while i <= y:
            count[i*Ksq:i*Ksq+x+1] += 1
            count[i*Ksq+x+K+1%Ksq:i*Ksq+Ksq] += 1
            i += 1
        i = y + K + 1
        while i < Ksq:
            count[i*Ksq:i*Ksq+x+1] += 1
            count[i*Ksq+x+K+1%Ksq:i*Ksq+Ksq] += 1
            i += 1
        i = K
        while i <= y + K:
            count[i*Ksq+x+1:i*Ksq+K] += 1
            count[i*Ksq+K:i*Ksq+K+x+1] += 1
            i += 1
        i = y + 1
        while i < K:
            count[i*Ksq+x+1:i*Ksq+K] += 1
            count[i*Ksq+K:i*Ksq+K+x+1] += 1
            i += 1
    else: # c == 'B'
        i = K
        while i <= y + K:
            count[i*Ksq:i*Ksq+x+1] += 1
            count[i*Ksq+x+K+1%Ksq:i*Ksq+Ksq] += 1
            i += 1
        i = y + 1
        while i < K:
            count[i*Ksq:i*Ksq+x+1] += 1
            count[i*Ksq+x+K+1%Ksq:i*Ksq+Ksq] += 1
            i += 1
        i = 0
        while i <= y:
            count[i*Ksq+x+1:i*Ksq+K] += 1
            count[i*Ksq+K:i*Ksq+K+x+1] += 1
            i += 1
        i = y + K + 1
        while i < Ksq:
            count[i*Ksq+x+1:i*Ksq+K] += 1
            count[i*Ksq+K:i*Ksq+K+x+1] += 1
            i += 1

print(max(count))

Submission status: Time Limit Exceeded

Solution code:
def main():
    """
    Range:
        (x,y)
        X: x-K+1 〜 x+K-1
        Y: y-K+1 〜 y+K-1

    rangeをすべて試す: 無理
        1つの希望を満たすように範囲指定:
            模様は確定する
                (0,0)-(K,K) * 2(W or B)
                K^2 * N -> 10^3^2 * 10^5
            他の希望は満たされるか判定
    """
    N, K = map(int, input().split())
    xy = []
    for _ in range(N):
        x, y, c = input().split()
        a = K if c == "B" else 0
        xy.append((int(x), int(y) + a))

    AC(K, xy)
    # TLE(K, xy)


def fix(x, K2):
    return min(max(0, x), K2)


def boundary(x, y, K):
    K2 = K * 2
    s = set()
    for i in range(-2, 2):
        for j in range(-2, 2):
            if (i + j) % 2 == 1:
                continue

            x1 = fix(x + i * K, K2)
            y1 = fix(y + j * K, K2)
            x2 = fix(x + (i + 1) * K, K2)
            y2 = fix(y + (j + 1) * K, K2)

            if x1 == x2 or y1 == y2:
                continue

            s.add(((x1, y1), (x2, y2)))

    return s

def AC(K, xy):
    K2 = K * 2
    w = [
        [0] * (K2 + 1)
        for _ in range(K2 + 1)
    ]

    for x, y in xy:
        x = x % K2
        y = y % K2
        for (x1, y1), (x2, y2) in boundary(x, y, K):
            w[y1][x1] += 1
            w[y1][x2] -= 1
            w[y2][x1] -= 1
            w[y2][x2] += 1

    import numpy as np
    ans = np.array(w).cumsum(axis=1).cumsum(axis=0).max()

    print(ans)


def TLE(K, xy):
    ans = 0
    for i in range(2 * K):
        for j in range(2 * K):
            tmp_ans = 0
            for x, y in xy:
                x = (x + i) % (2 * K)
                y = (y + j) % (2 * K)

                w1 = x < K and y < K
                w2 = x >= K and y >= K
                if w1 or w2:
                    tmp_ans += 1

            ans = max(ans, tmp_ans)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    """
    Range:
        (x,y)
        X: x-K+1 〜 x+K-1
        Y: y-K+1 〜 y+K-1

    rangeをすべて試す: 無理
        1つの希望を満たすように範囲指定:
            模様は確定する
                (0,0)-(K,K) * 2(W or B)
                K^2 * N -> 10^3^2 * 10^5
            他の希望は満たされるか判定
    """
    N, K = map(int, input().split())
    xy = []
    for _ in range(N):
        x, y, c = input().split()
        a = K if c == "B" else 0
        xy.append((int(x), int(y) + a))

    TLE(K, xy)


def TLE(K, xy):
    ans = 0
    for i in range(2 * K):
        for j in range(2 * K):
            tmp_ans = 0
            for x, y in xy:
                x = (x + i) % (2 * K)
                y = (y + j) % (2 * K)

                w1 = x < K and y < K
                w2 = x >= K and y >= K
                if w1 or w2:
                    tmp_ans += 1

            ans = max(ans, tmp_ans)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import sys


def color(x, y, k):
    r = 0
    k2 = k << 1
    if ((x % k2) / k) != 0:
        r = -1
    
    if ((y % k2) / k) != 0:
        r ^= -1

    return 'B' if  r == 0 else 'W'


n, k = [int(e) for e in raw_input().split()]
td = dict()
k2 = k << 1
for i in range(0, n):
    x, y, c = [e for e in raw_input().split()]
    v = td.setdefault((int(x) % k2, int(y) % k2, ), dict())
    v[c] = v.get(c, 0) + 1

# print
# print n, k
# print td

# for i in range(0, k2):
#     for j in range(0, k2):
#         print color(i, j, k),
#     print

maxH = 0
for yi in xrange(0, k2):
    for xi in xrange(0, k2):
        h = 0
        for tk, tv in td.iteritems():
            x, y = tk
            c = color(x + xi, y + yi, k)
            h += tv.get(c, 0)
        if h > maxH:
            maxH = h

sys.stdout.write('%d\n' % maxH)
sys.stdout.flush()

Submission status: Time Limit Exceeded

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

import sys

def color(x, y, k):
    r = 0
    if ((x % (2*k)) / k) != 0:
        r = -1
    
    if ((y % (2*k)) / k) != 0:
        r ^= -1

    return 'B' if  r == 0 else 'W'

def nSatisfied(n, k, tl):
    maxH = 0
    for yi in xrange(0, 2*k):
        for xi in xrange(0, 2*k):
            h = 0
            for e in tl:
                x, y, c = e
                if color(x + xi, y + yi, k) == c:
                    h += 1
            if h > maxH:
                maxH = h
            if maxH == n:
                return maxH
    return maxH


n, k = [int(e) for e in raw_input().split()]
tl = []
for i in range(0, n):
    x, y, c = [e for e in raw_input().split()]
    tl.append([int(x), int(y), c])

# print
# print n, k
# print tl

# for i in range(0, 2*k):
#     print color(i, k),

# print

maxH = nSatisfied(n, k, tl)

sys.stdout.write('%d\n' % maxH)
sys.stdout.flush()

Submission status: Time Limit Exceeded

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

import sys

def color(x, y, k):
    r = 0
    if ((x % (2*k)) / k) != 0:
        r = -1
    
    if ((y % (2*k)) / k) != 0:
        r ^= -1

    return 'B' if  r == 0 else 'W'

def nSatisfied(n, k, tl):
    maxH = 0
    for yi in range(0, 2*k):
        for xi in range(0, 2*k):
            h = 0
            for e in tl:
                x, y, c = e
                if color(x + xi, y + yi, k) == c:
                    h += 1
            if h > maxH:
                maxH = h
            if maxH == n:
                return maxH
    return maxH


n, k = [int(e) for e in raw_input().split()]
tl = []
for i in range(0, n):
    x, y, c = [e for e in raw_input().split()]
    tl.append([int(x), int(y), c])

# print
# print n, k
# print tl

# for i in range(0, 2*k):
#     print color(i, k),

# print

maxH = nSatisfied(n, k, tl)

sys.stdout.write('%d\n' % maxH)
sys.stdout.flush()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
B = [[0]*k for i in range(k)]
W = [[0]*k for i in range(k)]
for i in range(n):
    x, y, c = input().split(); x = int(x); y = int(y)
    x %= 2*k; y %= 2*k
    if (k <= x) == (k <= y):
        (B if c is 'B' else W)[y%k][x%k] += 1
    else:
        (W if c is 'B' else B)[y%k][x%k] += 1
def calc(M, n):
    D = [[0]*(n+1) for i in range(n+1)]
    for i in range(1, n+1):
        tmp = 0
        for j in range(1, n+1):
            tmp += M[i-1][j-1]
            D[i][j] = tmp + D[i-1][j]
    return D

# [a, c) * [b, d)
def su(D, a, b, c, d):
    return D[d][c] - D[d][a] - D[b][c] + D[b][a]

DB = calc(B, k)
DW = calc(W, k)
ans = 0
for i in range(k):
    for j in range(k):
        ans = max(ans, su(DB, 0, 0, i, j) + su(DB, i, j, k, k) + su(DW, i, 0, k, j) + su(DW, 0, j, i, k))
        ans = max(ans, su(DW, 0, 0, i, j) + su(DW, i, j, k, k) + su(DB, i, 0, k, j) + su(DB, 0, j, i, k))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def getBoundary(p, k, k2):
    if p - k + 1 >= 0:
        return [(p - k + 1, p + 1)]
    else:
        return [(0, p + 1), ((p - k + 1) % k2, k2)]

n, k = map(int, input().strip().split())
k2 = k * 2
b = np.zeros((k2 + 1, k2 + 1), dtype = np.int16)

for i in range(n):
    x_str, y_str, c_str = input().strip().split()
    x = int(x_str) % k2
    y = (int(y_str) + (c_str == 'B') * k) % k2
    for xb, xe in getBoundary(x % k2, k, k2):
        for yb, ye in getBoundary(y % k2, k, k2):
            b[xb, yb] += 1
            b[xb, ye] -= 1
            b[xe, yb] -= 1
            b[xe, ye] += 1
    for xb, xe in getBoundary((x + k) % k2, k, k2):
        for yb, ye in getBoundary((y + k) % k2, k, k2):
            b[xb, yb] += 1
            b[xb, ye] -= 1
            b[xe, yb] -= 1
            b[xe, ye] += 1

for i in range(k2):
    b[i + 1] += b[i]
for j in range(k2):
    b[:, j + 1] += b[:, j]
print(b.max())

Submission status: Time Limit Exceeded

Solution code:
#import time

nk = [int(x) for x in input().strip().split()]
d = []
for i in range(nk[0]):
    d_tmp = input().strip().split()
    d.append([int(d_tmp[0]), int(d_tmp[1]), int(d_tmp[2] == 'B')])

n1 = nk[0]
k1 = nk[1]

check_x = [0] * n1 * 4
check_y = [0] * n1 * 4
for i in range(n1):
    check_x[i * 4 + 1] = d[i][0] - k1 + 1
    check_x[i * 4 + 2] = d[i][0]
    check_y[i * 4 + 1] = d[i][1] - k1 + 1
    check_y[i * 4 + 2] = d[i][1]
check_x = list(set(check_x))
check_y = list(set(check_y))

#d = tuple(d)
n = 0
#t = time.clock()
#for i in range(k1):
#    for j in range(k1):
for i in check_x:
    for j in check_y:
        n_tmp = [0, 0]
        for k in range(n1):
            x = (d[k][0] - i) // k1 % 2
            y = (d[k][1] - j) // k1 % 2
#            if x == y:
#                n_tmp[1 - d[k][2]] += 1
#            else:
#                n_tmp[d[k][2]] += 1
            n_tmp[(x == y) ^ d[k][2]] += 1
        if n_tmp[0] > n:
            n = n_tmp[0]
        if n_tmp[1] > n:
            n = n_tmp[1]
#print(time.clock() - t)
print(n)

Submission status: Time Limit Exceeded

Solution code:
import time

nk = [int(x) for x in raw_input().strip().split()]
d = []
for i in range(nk[0]):
    d_tmp = raw_input().strip().split()
    d.append([int(d_tmp[0]), int(d_tmp[1]), int(d_tmp[2] == 'B')])

n1 = nk[0]
k1 = nk[1]

check_x = [0] * n1 * 4
check_y = [0] * n1 * 4
for i in range(n1):
    check_x[i * 4] = d[i][0] - k1
    check_x[i * 4 + 1] = d[i][0] - k1 + 1
    check_x[i * 4 + 2] = d[i][0]
    check_x[i * 4 + 3] = d[i][0] + 1
    check_y[i * 4] = d[i][1] - k1
    check_y[i * 4 + 1] = d[i][1] - k1 + 1
    check_y[i * 4 + 2] = d[i][1]
    check_y[i * 4 + 3] = d[i][1] + 1

#d = tuple(d)
n = 0
#t = time.clock()
for i in check_x:
    for j in check_y:
        n_tmp = [0, 0]
        for k in range(n1):
            x = (d[k][0] - i) // k1 % 2
            y = (d[k][1] - j) // k1 % 2
#            if x == y:
#                n_tmp[1 - d[k][2]] += 1
#            else:
#                n_tmp[d[k][2]] += 1
            n_tmp[(x == y) ^ d[k][2]] += 1
        if n_tmp[0] > n:
            n = n_tmp[0]
        if n_tmp[1] > n:
            n = n_tmp[1]
#print time.clock() - t
print n

Submission status: Time Limit Exceeded

Solution code:
import time

nk = [int(x) for x in raw_input().strip().split()]
d = []
for i in range(nk[0]):
    d_tmp = raw_input().strip().split()
    d.append([int(d_tmp[0]), int(d_tmp[1]), int(d_tmp[2] == 'B')])

n1 = nk[0]
k1 = nk[1]

check_x = [0] * n1 * 4
check_y = [0] * n1 * 4
for i in range(n1):
    check_x[i * 4] = d[i][0] - k1
    check_x[i * 4 + 1] = d[i][0] - k1 + 1
    check_x[i * 4 + 2] = d[i][0]
    check_x[i * 4 + 3] = d[i][0] + 1
    check_y[i * 4] = d[i][1] - k1
    check_y[i * 4 + 1] = d[i][1] - k1 + 1
    check_y[i * 4 + 2] = d[i][1]
    check_y[i * 4 + 3] = d[i][1] + 1
check_x = list(set(check_x))
check_y = list(set(check_y))

#d = tuple(d)
n = 0
#t = time.clock()
for i in check_x:
    for j in check_y:
        n_tmp = [0, 0]
        for k in range(n1):
            x = (d[k][0] - i) // k1 % 2
            y = (d[k][1] - j) // k1 % 2
#            if x == y:
#                n_tmp[1 - d[k][2]] += 1
#            else:
#                n_tmp[d[k][2]] += 1
            n_tmp[(x == y) ^ d[k][2]] += 1
        if n_tmp[0] > n:
            n = n_tmp[0]
        if n_tmp[1] > n:
            n = n_tmp[1]
#print time.clock() - t
print n

Submission status: Time Limit Exceeded

Solution code:
import time

nk = [int(x) for x in raw_input().strip().split()]
d = []
for i in range(nk[0]):
    d_tmp = raw_input().strip().split()
    d.append([int(d_tmp[0]), int(d_tmp[1]), int(d_tmp[2] == 'B')])

n1 = nk[0]
k1 = nk[1]

check_x = []
check_y = []
for i in range(n1):
    check_x.extend([d[i][0] - k1, d[i][0] - k1 + 1, d[i][0], d[i][0] + 1])
    check_y.extend([d[i][1] - k1, d[i][1] - k1 + 1, d[i][1], d[i][1] + 1])
#check_x = list(set(check_x))
#check_y = list(set(check_y))

#d = tuple(d)
n = 0
#t = time.clock()
for i in check_x:
    for j in check_y:
        n_tmp = [0, 0]
        for k in range(n1):
            x = (d[k][0] - i) // k1 % 2
            y = (d[k][1] - j) // k1 % 2
#            if x == y:
#                n_tmp[1 - d[k][2]] += 1
#            else:
#                n_tmp[d[k][2]] += 1
            n_tmp[(x == y) ^ d[k][2]] += 1
        if n_tmp[0] > n:
            n = n_tmp[0]
        if n_tmp[1] > n:
            n = n_tmp[1]
#print time.clock() - t
print n

Submission status: Time Limit Exceeded

Solution code:
#import time

nk = [int(x) for x in raw_input().strip().split()]
d = []
for i in range(nk[0]):
    d_tmp = raw_input().strip().split()
    d.append([int(d_tmp[0]), int(d_tmp[1]), int(d_tmp[2] == 'B')])

n1 = nk[0]
k1 = nk[1]

check_x = []
check_y = []
for i in range(n1):
    check_x.extend([d[i][0] - k1, d[i][0] - k1 + 1, d[i][0], d[i][0] + 1])
    check_y.extend([d[i][1] - k1, d[i][1] - k1 + 1, d[i][1], d[i][1] + 1])
check_x = list(set(check_x))
check_y = list(set(check_y))

#d = tuple(d)
n = 0
#t = time.clock()
for i in check_x:
    for j in check_y:
        n_tmp = [0, 0]
        for k in range(n1):
            x = (d[k][0] - i) // k1 % 2
            y = (d[k][1] - j) // k1 % 2
#            if x == y:
#                n_tmp[1 - d[k][2]] += 1
#            else:
#                n_tmp[d[k][2]] += 1
            n_tmp[(x == y) ^ d[k][2]] += 1
        if n_tmp[0] > n:
            n = n_tmp[0]
        if n_tmp[1] > n:
            n = n_tmp[1]
#print time.clock() - t
print n

Submission status: Time Limit Exceeded

Solution code:
#import time

nk = [int(x) for x in raw_input().strip().split()]
d = []
for i in range(nk[0]):
    d_tmp = raw_input().strip().split()
    d.append([int(d_tmp[0]), int(d_tmp[1]), int(d_tmp[2] == 'B')])

n1 = nk[0]
k1 = nk[1]

#d = tuple(d)
n = 0
#t = time.clock()
for i in range(k1):
    for j in range(k1):
        n_tmp = [0, 0]
        for k in range(n1):
            x = (d[k][0] - i) // k1 % 2
            y = (d[k][1] - j) // k1 % 2
#            if x == y:
#                n_tmp[1 - d[k][2]] += 1
#            else:
#                n_tmp[d[k][2]] += 1
            n_tmp[(x == y) ^ d[k][2]] += 1
        if n_tmp[0] > n:
            n = n_tmp[0]
        if n_tmp[1] > n:
            n = n_tmp[1]
#print time.clock() - t
print n

Submission status: Time Limit Exceeded

Solution code:
#import time

nk = [int(x) for x in raw_input().strip().split()]
d = []
for i in range(nk[0]):
    d_tmp = raw_input().strip().split()
    d.append([int(d_tmp[0]), int(d_tmp[1]), int(d_tmp[2] == 'B')])

n1 = nk[0]
k1 = nk[1]
k2 = k1 * 2

d = tuple(d)
n = 0
#t = time.clock()
for i in range(k1):
    for j in range(k1):
        n_tmp = [0, 0]
        for k in range(n1):
            x = (d[k][0] - i) // k1 % 2
            y = (d[k][1] - j) // k1 % 2
            if x == y:
                n_tmp[1 - d[k][2]] += 1
            else:
                n_tmp[d[k][2]] += 1
        if n_tmp[0] > n:
            n = n_tmp[0]
        if n_tmp[1] > n:
            n = n_tmp[1]
#print time.clock() - t
print n

Submission status: Time Limit Exceeded

Solution code:
#import time

nk = [int(x) for x in raw_input().strip().split()]
d = []
for i in range(nk[0]):
    d_tmp = raw_input().strip().split()
    d.append([int(d_tmp[0]), int(d_tmp[1]), int(d_tmp[2] == 'B')])

n1 = nk[0]
k1 = nk[1]
k2 = k1 * 2

#d = tuple(d)
n = 0
#t = time.clock()
for i in range(k1):
    for j in range(k1):
        n_tmp = [0, 0]
        for k in range(n1):
            x = (d[k][0] - i) // k1 % 2
            y = (d[k][1] - j) // k1 % 2
            if x == y:
                n_tmp[1 - d[k][2]] += 1
            else:
                n_tmp[d[k][2]] += 1
        if n_tmp[0] > n:
            n = n_tmp[0]
        if n_tmp[1] > n:
            n = n_tmp[1]
#print time.clock() - t
print n

Submission status: Time Limit Exceeded

Solution code:
nk = [int(x) for x in raw_input().strip().split()]
d = []
for i in range(nk[0]):
    d_tmp = raw_input().strip().split()
    d.append([int(d_tmp[0]), int(d_tmp[1]), d_tmp[2]])

n1 = nk[0]
k1 = nk[1]
k2 = k1 * 2

n = 0
#for i in range(k2):
#    for j in range(k2):
#        n_tmp = 0
#        for k in range(n1):
#            x = (d[k][0] - i) // k1 % 2
#            y = (d[k][1] - j) // k1 % 2
#            if x == y and d[k][2] == 'B':
#                n_tmp += 1
#            elif x != y and d[k][2] == 'W':
#                n_tmp += 1
#        if n_tmp > n:
#            n = n_tmp
for i in range(k1):
    for j in range(k1):
        n_tmp = [0, 0]
        for k in range(n1):
            x = (d[k][0] - i) // k1 % 2
            y = (d[k][1] - j) // k1 % 2
            if x == y and d[k][2] == 'B':
                n_tmp[0] += 1
            elif x != y and d[k][2] == 'W':
                n_tmp[0] += 1
            if x == y and d[k][2] == 'W':
                n_tmp[1] += 1
            elif x != y and d[k][2] == 'B':
                n_tmp[1] += 1
        if n_tmp[0] > n:
            n = n_tmp[0]
        if n_tmp[1] > n:
            n = n_tmp[1]
        n_tmp = 0

print n

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# coding=utf-8

import sys

import numpy as np

n, k = map(int, sys.stdin.readline().strip().split(" "))
xyc = [l.strip().split(" ") for l in sys.stdin.readlines()]
xy = [(int(_x) % (2 * k), int(_y) % (2 * k) if _c == "W" else (int(_y) + k) % (2 * k))
      for (_x, _y, _c) in xyc]

ans = np.zeros((2 * k, 2 * k), dtype=np.int32)
for _x, _y in xy:
    if (_x - k + 0.5) * (_y - k + 0.5) > 0:
        _x %= k
        _y %= k
        ans[_x, _y] += 2
        ans[_x + k, _y] -= 2
        ans[_x, _y + k] -= 2
        ans[_x + k, _y + k] += 2
        ans[_x + k, 0] += 1
        ans[0, _y + k] += 1
        ans[0, 0] += 1
        ans[_x, 0] -= 1
        ans[0, _y] -= 1
    else:
        _x %= k
        _y %= k
        ans[_x, _y] -= 2
        ans[_x + k, _y] += 2
        ans[_x, _y + k] += 2
        ans[_x + k, _y + k] -= 2
        ans[_x + k, 0] -= 1
        ans[0, _y + k] -= 1
        ans[_x, 0] += 1
        ans[0, _y] += 1
print(ans.cumsum(axis=1).cumsum(axis=0).max())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# coding=utf-8

import sys

import numpy as np

n, k = map(int, sys.stdin.readline().strip().split(" "))
xyc = [l.strip().split(" ") for l in sys.stdin.readlines()]
xy = [tuple((int(_x), int(_y) if _c == "W" else int(_y) + k)) for (_x, _y, _c) in xyc]
xy = [tuple((_x % (2 * k), _y % (2 * k))) for (_x, _y) in xy]

ans = np.zeros((2 * k, 2 * k), dtype=np.int32)
for _x, _y in xy:
    if (_x - k + 0.5) * (_y - k + 0.5) > 0:
        _x %= k
        _y %= k
        ans[_x, _y] += 2
        ans[_x + k, _y] -= 2
        ans[_x, _y + k] -= 2
        ans[_x + k, _y + k] += 2
        ans[_x + k, 0] += 1
        ans[0, _y + k] += 1
        ans[0, 0] += 1
        ans[_x, 0] -= 1
        ans[0, _y] -= 1
    else:
        _x %= k
        _y %= k
        ans[_x, _y] -= 2
        ans[_x + k, _y] += 2
        ans[_x, _y + k] += 2
        ans[_x + k, _y + k] -= 2
        ans[_x + k, 0] -= 1
        ans[0, _y + k] -= 1
        ans[_x, 0] += 1
        ans[0, _y] += 1
print(np.max(ans.cumsum(axis=1).cumsum(axis=0)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# coding=utf-8

import sys

import numpy as np

n, k = map(int, sys.stdin.readline().strip().split(" "))
xyc = [l.strip().split(" ") for l in sys.stdin.readlines()]
xy = [tuple((int(_x), int(_y) if _c == "W" else int(_y) + k)) for (_x, _y, _c) in xyc]
xy = [tuple((_x % (2 * k), _y % (2 * k))) for (_x, _y) in xy]

ans = np.zeros((2 * k, 2 * k), dtype=np.int32)
for _x, _y in xy:
    if (_x - k + 0.5) * (_y - k + 0.5) > 0:
        _x %= k
        _y %= k
        ans[_x, _y] += 1
        ans[_x + k, _y] -= 1
        ans[_x, _y + k] -= 1
        ans[_x + k, _y + k] += 1
        ans[_x + k, _y + k] += 1
        ans[_x + k, 0] += 1
        ans[_x + k, _y] -= 1
        ans[0, _y + k] += 1
        ans[_x, _y + k] -= 1
        ans[0, 0] += 1
        ans[_x, 0] -= 1
        ans[0, _y] -= 1
        ans[_x, _y] += 1
    else:
        _x %= k
        _y %= k
        ans[_x, _y] -= 1
        ans[_x + k, _y] += 1
        ans[_x, _y + k] += 1
        ans[_x + k, _y + k] -= 1
        ans[_x + k, _y + k] -= 1
        ans[_x + k, 0] -= 1
        ans[_x + k, _y] += 1
        ans[0, _y + k] -= 1
        ans[_x, _y + k] += 1
        # ans[0, 0] -= 1
        ans[_x, 0] += 1
        ans[0, _y] += 1
        ans[_x, _y] -= 1
print(np.max(ans.cumsum(axis=1).cumsum(axis=0)))