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:
#!/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:
    check = np.zeros((2 * k, 2 * k), dtype=np.int32)
    check[_x:_x + k] = 1
    if _x > k:
        check[:_x - k] = 1
    check[:, _y:_y + k] = 1 - check[:, _y:_y + k]
    if _y > k:
        check[:, :_y - k] = 1 - check[:, :_y - k]
    check = 1 - check
    ans += check
print(np.max(ans))

Submission status: Time Limit Exceeded

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

import itertools
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()]
xyc = [tuple((int(_x), int(_y), _c == "W")) for (_x, _y, _c) in xyc]
xyc = [
    tuple((_x % k, _y % k, _c if (_x // k + _y // k) % 2 == 0 else not _c)) for (_x, _y, _c) in xyc
]

xs = np.asarray([_x for (_x, _y, _c) in xyc])
ys = np.asarray([_y for (_x, _y, _c) in xyc])
cs = np.asarray([_c for (_x, _y, _c) in xyc])
checks = np.asarray([
    np.logical_not(np.logical_xor((xs - i - 0.5) * (ys - j - 0.5) > 0, cs)) == f
    for i, j, f in itertools.product(set(xs), set(ys), {True, False})
])
print(max(np.sum(checks, axis=1)))

Submission status: Time Limit Exceeded

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

import itertools
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()]
xyc = [tuple((int(_x), int(_y), _c == "W")) for (_x, _y, _c) in xyc]
xyc = [
    tuple((_x % k, _y % k, _c if (_x // k + _y // k) % 2 == 0 else not _c)) for (_x, _y, _c) in xyc
]


def checker(base, condition):
    i, j, f = base
    x, y, c = condition
    if not ((x <= i and y <= j) or (i < x and j < y)):
        f = not f
    return f == c


xs = np.asarray([_x for (_x, _y, _c) in xyc])
ys = np.asarray([_y for (_x, _y, _c) in xyc])
cs = np.asarray([_c for (_x, _y, _c) in xyc])
checks = np.asarray([
    np.logical_not(np.logical_xor((xs - i - 0.5) * (ys - j - 0.5) > 0, cs)) == f
    for i, j, f in itertools.product(range(k), range(k), {True, False})
])
print(max(np.sum(checks, axis=1)))

Submission status: Time Limit Exceeded

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

import itertools
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()]
xyc = [tuple((int(_x), int(_y), _c == "W")) for (_x, _y, _c) in xyc]
xyc = [
    tuple((_x % k, _y % k, _c if (_x // k + _y // k) % 2 == 0 else not _c)) for (_x, _y, _c) in xyc
]


def checker(base, condition):
    i, j, f = base
    x, y, c = condition
    if not ((x <= i and y <= j) or (i < x and j < y)):
        f = not f
    return f == c


xs = np.asarray([_x for (_x, _y, _c) in xyc])
ys = np.asarray([_y for (_x, _y, _c) in xyc])
cs = np.asarray([_c for (_x, _y, _c) in xyc])
ans = 0
for i, j, f in itertools.product(set(xs), set(ys), {True, False}):
    checks = np.logical_not(np.logical_xor((xs - i - 0.5) * (ys - j - 0.5) > 0, cs)) == f
    # checks = [checker((i, j, f), _xyc) for _xyc in xyc]
    ans = max(ans, sum(checks))
    if ans == n:
        break
print(ans)

Submission status: Time Limit Exceeded

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

import itertools
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()]
xyc = [tuple((int(_x), int(_y), _c == "W")) for (_x, _y, _c) in xyc]
xyc = [
    tuple((_x % k, _y % k, _c if (_x // k + _y // k) % 2 == 0 else not _c)) for (_x, _y, _c) in xyc
]


def checker(base, condition):
    i, j, f = base
    x, y, c = condition
    if not ((x <= i and y <= j) or (i < x and j < y)):
        f = not f
    return f == c


xs = {_x for (_x, _y, _c) in xyc}
ys = {_y for (_x, _y, _c) in xyc}

ans = 0
for i, j, f in itertools.product(xs, ys, {True, False}):
    checks = [checker((i, j, f), _xyc) for _xyc in xyc]
    ans = max(ans, sum(checks))
    if ans == n:
        break
print(ans)

Submission status: Time Limit Exceeded

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

import itertools
import sys

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


def checker(base, condition):
    i, j, f = base
    x, y, c = condition
    if not ((x <= i and y <= j) or (i < x and j < y)):
        f = not f
    return f == c


ans = 0
for i, j, f in itertools.product(range(k), range(k), {True, False}):
    checks = [checker((i, j, f), _xyc) for _xyc in xyc]
    ans = max(ans, sum(checks))
    if ans == n:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, raw_input().split())
x,y,c=[],[],[]
K2=2*K
xx,yy=[],[]

for i in range(N):
    x0,y0,col = raw_input().split()
    x.append(int(x0))
    y.append(int(y0))
    c.append(col)

    x0=int(x0)%K
    y0=int(y0)%K
    xx.append(x0)
    yy.append(y0)
   
xmin,xmax=min(xx),max(xx)
ymin,ymax=min(yy),max(yy)

countmax=0
for a in set(xx):
    for b in set(yy):
        okc1,okc2=0,0
        for i in range(N):
            x1=(x[i]-a)%K2
            y1=(y[i]-b)%K2

            ok1,ok2=1,1

            q=(x1/K)==0 #q=(0<=x1 and x1<K)
            r=(y1/K)==1 #r=(K<=y1 and y1<K2)
            s=(x1/K)==1 #s=(K<=x1 and x1<K2)
            t=(y1/K)==0 #t=( 0<=y1 and y1<K)

            if (c[i]=="B") :
               if ((q and r) or (s and t)) : ok1=0
               if ((q and t) or (s and r)) : ok2=0
            if (c[i]=="W") : 
               if ((q and r) or (s and t)) : ok2=0
               if ((q and t) or (s and r)) : ok1=0
            okc1=okc1+ok1
            okc2=okc2+ok2

        if (countmax<okc1) :countmax=okc1 
        if (countmax<okc2) :countmax=okc2
        if (countmax==N) :break
    if(countmax==N):break

print countmax

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, raw_input().split())
x,y,c=[],[],[]
K2=2*K
xx,yy=[],[]

for i in range(N):
    x0,y0,col = raw_input().split()
    x.append(int(x0))
    y.append(int(y0))
    c.append(col)

    x0=int(x0)%K
    y0=int(y0)%K
    xx.append(x0)
    yy.append(y0)
   
xmin,xmax=min(xx),max(xx)
ymin,ymax=min(yy),max(yy)

countmax=0
for a in range(xmin,xmax+1):
    for b in range(ymin,ymax+1):
        okc1,okc2=0,0
        for i in range(N):
            x1=(x[i]-a)%K2
            y1=(y[i]-b)%K2

            ok1,ok2=1,1

            q=(x1/K)==0 #q=(0<=x1 and x1<K)
            r=(y1/K)==1 #r=(K<=y1 and y1<K2)
            s=(x1/K)==1 #s=(K<=x1 and x1<K2)
            t=(y1/K)==0 #t=( 0<=y1 and y1<K)

            if (c[i]=="B") :
               if ((q and r) or (s and t)) : ok1=0
               if ((q and t) or (s and r)) : ok2=0
            if (c[i]=="W") : 
               if ((q and r) or (s and t)) : ok2=0
               if ((q and t) or (s and r)) : ok1=0
            okc1=okc1+ok1
            okc2=okc2+ok2

        if (countmax<okc1) :countmax=okc1 
        if (countmax<okc2) :countmax=okc2
        if (countmax==N) :break
    if(countmax==N):break

print countmax

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, raw_input().split())
x,y,c=[],[],[]
K2=2*K

for i in range(N):
    x0,y0,col = raw_input().split()
    x.append(int(x0))
    y.append(int(y0))
    c.append(col)

countmax=0
for a in range(K):
    for b in range(K):
        okc1,okc2=0,0
        for i in range(N):
            x1=(x[i]-a)%K2
            y1=(y[i]-b)%K2

            ok1,ok2=1,1

            q=(x1/K)==0 #q=(0<=x1 and x1<K)
            r=(y1/K)==1 #r=(K<=y1 and y1<K2)
            s=(x1/K)==1 #s=(K<=x1 and x1<K2)
            t=(y1/K)==0 #t=( 0<=y1 and y1<K)

            if (c[i]=="B") :
               if ((q and r) or (s and t)) : ok1=0
               if ((q and t) or (s and r)) : ok2=0
            if (c[i]=="W") : 
               if ((q and r) or (s and t)) : ok2=0
               if ((q and t) or (s and r)) : ok1=0
            okc1=okc1+ok1
            okc2=okc2+ok2
            if ( okc1+(N-1-i)<=countmax and okc2+(N-1-i)<=countmax ):break 

        if (countmax<okc1) :countmax=okc1 
        if (countmax<okc2) :countmax=okc2
        if (countmax==N) :break
    if(countmax==N):break

print countmax

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, raw_input().split())
x,y,c=[],[],[]
K2=2*K

for i in range(N):
    x0,y0,col = raw_input().split()
    x.append(int(x0))
    y.append(int(y0))
    c.append(col)

countmax=0
for a in range(K):
    for b in range(K):
        okc1,okc2=0,0
        for i in range(N):
            x1=(x[i]-a)%K2
            y1=(y[i]-b)%K2

            ok1,ok2=1,1

            q=(x1/K)==0 #q=(0<=x1 and x1<K)
            r=(y1/K)==1 #r=(K<=y1 and y1<K2)
            s=(x1/K)==1 #s=(K<=x1 and x1<K2)
            t=(y1/K)==0 #t=( 0<=y1 and y1<K)

            if (c[i]=="B") :
               if ((q and r) or (s and t)) : ok1=0
               if ((q and t) or (s and r)) : ok2=0
            if (c[i]=="W") : 
               if ((q and r) or (s and t)) : ok2=0
               if ((q and t) or (s and r)) : ok1=0
            okc1=okc1+ok1
            okc2=okc2+ok2

        if (countmax<okc1) :countmax=okc1 
        if (countmax<okc2) :countmax=okc2
        if (countmax==N) :break
    if(countmax==N):break

print countmax

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, raw_input().split())
x,y,c=[],[],[]
K2=2*K

for i in range(N):
    x0,y0,col = raw_input().split()
    x.append(int(x0))
    y.append(int(y0))
    c.append(col)

countmax=0
for a in range(K):
    for b in range(K):
        okc1,okc2=0,0
        for i in range(N):
            x1=(x[i]-a)%K2
            y1=(y[i]-b)%K2

            ok1,ok2=1,1

            q=(0<=x1 and x1<K)
            r=(K<=y1 and y1<K2)
            s=(K<=x1 and x1<K2)
            t=( 0<=y1 and y1<K)

            if (c[i]=="B") :
               if ((q and r) or (s and t)) : ok1=0
               if ((q and t) or (s and r)) : ok2=0
            if (c[i]=="W") : 
               if ((q and r) or (s and t)) : ok2=0
               if ((q and t) or (s and r)) : ok1=0
            okc1=okc1+ok1
            okc2=okc2+ok2

        if (countmax<okc1) :countmax=okc1 
        if (countmax<okc2) :countmax=okc2
        if (countmax==N) :break
    if(countmax==N):break

print countmax

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, raw_input().split())
x,y,c=[],[],[]
K2=2*K

for i in range(N):
    x0,y0,col = raw_input().split()
    x.append(int(x0))
    y.append(int(y0))
    c.append(col)

countmax=0
for a in range(K):
    for b in range(K):
        okc1,okc2=0,0
        for i in range(N):
            x1=(x[i]-a)%K2
            y1=(y[i]-b)%K2

            ok1,ok2=1,1
            if (c[i]=="B") :
               if ((0<=x1 and x1<K and K<=y1 and y1<K2) or (K<=x1 and x1<K2 and 0<=y1 and y1<K)) : ok1=0
               if ((0<=x1 and x1<K and 0<=y1 and y1<K) or (K<=x1 and x1<K2 and K<=y1 and y1<K2)) : ok2=0
            if (c[i]=="W") : 
               if ((0<=x1 and x1<K and K<=y1 and y1<K2) or (K<=x1 and x1<K2 and 0<=y1 and y1<K)) : ok2=0
               if ((0<=x1 and x1<K and 0<=y1 and y1<K) or (K<=x1 and x1<K2 and K<=y1 and y1<K2)) : ok1=0
            okc1=okc1+ok1
            okc2=okc2+ok2

        if (countmax<okc1) :countmax=okc1 
        if (countmax<okc2) :countmax=okc2
        if (countmax==N) :break
    if(countmax==N):break

print countmax

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, K = map(int, input().split())
ub = K * 2
b = np.zeros((ub + 1, ub + 1), int)

def create_bound(p):
	if p - K + 1 >= 0:
		return [(p - K + 1, p + 1)]
	else:
		return [(0, p + 1), ((p - K + 1) % ub, ub)]

for i in range(N):
	x, y, c = input().split()
	nx = int(x) % ub
	ny = (int(y) + (K if c == "W" else 0)) % ub
	for add in [0, K]:
		for xlb, xub in create_bound((nx + add) % ub):
			for ylb, yub in create_bound((ny + add) % ub):
				b[xlb][ylb] += 1
				b[xlb][yub] -= 1
				b[xub][ylb] -= 1
				b[xub][yub] += 1

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

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, raw_input().split())
x,y,c=[],[],[]
K2=2*K

for i in range(N):
    x0,y0,col = raw_input().split()
    x.append(int(x0))
    y.append(int(y0))
    c.append(col)

countmax=0
for a in range(K):
    for b in range(K):
        okc1,okc2=0,0
        for i in range(N):
            x1=(x[i]-a)%K2
            y1=(y[i]-b)%K2

            ok1,ok2=1,1
            if (c[i]=="B" and ( (0<=x1 and x1<K and K<=y1 and y1<K2) or (K<=x1 and x1<K2 and 0<=y1 and y1<K))) : ok1=0
            if (c[i]=="B" and ( (0<=x1 and x1<K and 0<=y1 and y1<K) or (K<=x1 and x1<K2 and K<=y1 and y1<K2))) : ok2=0

            if (c[i]=="W" and ( (0<=x1 and x1<K and K<=y1 and y1<K2) or (K<=x1 and x1<K2 and 0<=y1 and y1<K))) : ok2=0
            if (c[i]=="W" and ( (0<=x1 and x1<K and 0<=y1 and y1<K) or (K<=x1 and x1<K2 and K<=y1 and y1<K2))) : ok1=0
            okc1=okc1+ok1
            okc2=okc2+ok2

        if (countmax<okc1) :countmax=okc1 
        if (countmax<okc2) :countmax=okc2
        if (countmax==N) :break
    if(countmax==N):break

print countmax

Submission status: Time Limit Exceeded

Solution code:
#二次元累積和を用いる。

def query(x1,y1,x2,y2):
	""" (x2,y2) : 右上の点,(x1,y1) : 左下の点 """
	return arr[x2][y2] - arr[x2][y1-1] - arr[x1-1][y2] + arr[x1-1][y1-1]

N , K = map(int,input().split(" "))
arr = [[0] * (4*K) for _ in range(4*K)]

for i in range(N):
	x,y,c = map(str,input().split(" "))
	# 2K * 2K の座標サイズに圧縮。
	x = int(x) % (2*K)
	y = int(y) % (2*K)

	# Whiteの情報をBlackに変換
	if c == 'W':
		x += K
		x %= (2*K)

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


#累積和をとる。
for i in range(4*K):
	for j in range(4*K-1):
		arr[i][j+1] += arr[i][j]

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

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

print(ans)

Submission status: Time Limit Exceeded

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

W_sum = [[0 for i in range(K)] for j in range(K)]
B_sum = [[0 for i in range(K)] for j in range(K)]
for i in range(K):
    w = 0
    b = 0
    for j in range(K):
        w += W[i][j]
        b += B[i][j]
        W_sum[i][j] = w
        B_sum[i][j] = b
for i in range(K):
    w = 0
    b = 0
    for j in range(K):
        w += W_sum[j][i]
        b += B_sum[j][i]
        W_sum[j][i] = w
        B_sum[j][i] = b 
ans = 0
for i in range(K):
    for j in range(K):
        n = W_sum[K - 1][K - 1] + 2 * W_sum[i][j] - W_sum[i][K - 1] - W_sum[K - 1][j] + B_sum[i][K - 1] + B_sum[K - 1][j] - 2 * B_sum[i][j]
        ans = max(ans, max(n, N - n))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: UTF-8
def cumulativeSum(table):
#数値からなる2次元配列を受け取る:NxMのマトリックスでなければならない
#左上[0][0]要素から開始する累積和の2次元配列を返却する
#もとのtableが変更され、かつ返却される（副作用がある）ことに注意

  N = len(table)
  M = len(table[0])
  for i in range(N):
    for j in range(M):
      if i == 0:
        if j!=0:
          table[i][j] = table[i][j] + table[i][j-1]
      else:
        if j == 0:
          table[i][j] = table[i][j] + table[i-1][j]
        else:
          table[i][j] = table[i][j] + table[i][j-1] + table[i-1][j] - table[i-1][j-1]
  return table

def calcSum(i1,j1,i2,j2,ctable):
  #2つの座標と計算済み2次元累積和テーブルを受け取って、2つの座標によってつくられる長方形内の和を返す。副作用なし。
  #i1
  #j1
  #i2
  #j2
  I1 = min(i1,i2)
  J1 = min(j1,j2)
  I2 = max(i1,i2)
  J2 = max(j1,j2)
  
  A=0
  B=0
  C=0
  if J1 != 0:
    A = ctable[I2][J1-1]
  if I1 != 0 :
    B = ctable[I1-1][J2]
  if I1 != 0 and J1 != 0:
    C = ctable[I1-1][J1-1]
  
  return ctable[I2][J2] - A - B + C

def getIntervals(i,K):
  #0から2K-1の間のiとKを受け取る。区間とパリティのペアを返す。
  if i == 0:
    return [(0,K-1,0),(K,2*K-1,1)]
  elif i < K:
    return [(0,i-1,1),(i,i+K-1,0),(i+K,2*K-1,1)]
  elif i == K:
    return [(0,K-1,1),(K,2*K-1,0)]
  else:
    return [(0,i-K-1,0),(i-K,i-1,1),(i,2*K-1,0)]

def bTuples(i,j,K):
  #黒領域の左上の座標およびKの値を入力すると、calcSumに与えるべき座標値をtupleのリストとして返す。副作用なし。
  list = []
  xlist = getIntervals(i,K)
  ylist = getIntervals(j,K)
  
  for x in xlist:
    for y in ylist:
      i1,i2,px=x
      j1,j2,py=y
      if (px + py) % 2 == 0:
        list.append((i1,j1,i2,j2))
  
  return list

def solve():
  raw = list(map(int,input().split(" ")))
  N = raw[0]
  K = raw[1]
  
  length = 2*K
  gain=[[0 for _ in range(length)] for _ in range(length)]
  r=range(length)
  
  for i in range(N):
    raw = list(input().split(" "))
    x = int(raw[0])
    y = int(raw[1]) % (2*K)
    c = raw[2].strip('\r\n')
    if c == 'W':
      x = x + K
    x = x % (2*K)
    
    gain[x][y] = gain[x][y] + 1
    
  #sum of gain table
  cumulativeSum(gain)
  
  score = 0
  for i in range(2*K):
    for j in range(2*K):
      cand = 0
      for tuple in bTuples(i,j,K):
        i1,j1,i2,j2 = tuple
        cand += calcSum(i1,j1,i2,j2,gain)
      score = max(score,cand)
  return score

if __name__ == '__main__':
  
  ans = solve()
  print(ans, flush=True)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
co = []
result = []
def int_or_digit(a):
    if a.isdigit():
        return(int(a))
    else:
        return a
    
for i in range(n):
    d = tuple(map(int_or_digit,input().split()))
    if d[2] == "W":
        co.append((d[0],d[1]+k))
    else:
        co.append((d[0],d[1]))
from itertools import product

for i,j in product(range(2*k),repeat=2):
    count = 0
    for x,y in co:
        if ((x-i)//k + (y-j)//k)%2 == 0:
            count += 1
            
    result.append(count)
print(str(max(result)))

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
from operator import mul

# 整数Nを桁ごとのリストにする
# l = [int(x) for x in list(str(N))]

# リストliから重複を削除したリストli_uniqを作成
#li_uniq = []
#for i in li:
#    if x not in li_uniq:
#        li_uniq.append(x)

# 複数行のinput - list版
#list = [list(map(int, input().split())) for i in range(N)]
# 複数行のinput - dictionary版
# key = a, value = b
#for i in range(N):
#    a, b = map(int, input().split())
#    dict[a] = b


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

req = []
x_min = y_min = 0
for i in range(N):
    x, y, c = input().split()
    if int(x) <= x_min: x_min = int(x)
    if int(y) <= y_min: y_min = int(y)
    req = req + [[int(x), int(y), c]]


#平行移動して第一象限へ
for i in range(N):
    req[i][0] = req[i][0] - x_min
    req[i][1] = req[i][1] - y_min

#市松模様の白の起点を(-i, -j)として総当り
n_max = 0
for i in range(K): #xを移動
    for j in range(K): #yを移動
        n = 0
        for k in range(N):
            if ((req[k][0] + i) // K) % 2 == 0:
                if ((req[k][1] + j) // K) % 2 == 0: #(x, y)はW
                    if req[k][2] == 'W': n += 1
                else:
                    if req[k][2] == 'B': n += 1
            else:
                if ((req[k][1] + j) // K) % 2 == 0: #(x, y)はB
                    if req[k][2] == 'B': n += 1
                else:
                    if req[k][2] == 'W': n += 1
        if n >= n_max or (N - n) >= n_max:
            n_max = max(n, N-n)

print(n_max)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
x, y, c = [0]*N, [0]*N, [0]*N

for i in range(N):
	sx,sy,c[i] = map(str,input().split())
	x[i],y[i] = int(sx),int(sy)

cum_sum = [[0 for i in range(2*K+1)] for _ in range(2*K+1)]

def add(y, x, d):
	global cum_sum
	x += 1
	y += 1
	cum_sum[y][x] += d

def build():
	global K, cum_sum
	for i in range(1, 2*K+1):
		for j in range(1, 2*K+1):
			cum_sum[i][j] += cum_sum[i][j-1] + cum_sum[i-1][j] - cum_sum[i-1][j-1]

def count(left, right, top, bottom):
	global cum_sum
	res = cum_sum[bottom][right]
	res -= cum_sum[bottom][left]
	res -= cum_sum[top][right]
	res += cum_sum[top][left] 
	return res

for i in range(N):
	if c[i] == 'W':
		add(x[i] % (2*K), (y[i] + K) % (2*K), 1)
	else:
		add(x[i] % (2*K), y[i] % (2*K), 1)

build()
res = 0
for y in range(K):
	for x in range(K):
		curr = 0
		curr += count(0, x, 0, y)
		curr += count(0, x, y + K, 2*K)
		curr += count(x, x + K, y, y + K)
		curr += count(x + K, 2*K, 0, y)
		curr += count(x + K, 2*K, y + K, 2*K)
		res = max(res, curr)
		res = max(res, N - curr)

print(res)

Submission status: Time Limit Exceeded

Solution code:
def det(x,K):
  return x % (2*K) in range(K)

def isblack(x,y,K):
  return (det(x,K) and det(y,K)) or (not (det(x,K) or det(y,K)))

def solve():
  raw = list(map(int,input().split(" ")))
  N = raw[0]
  K = raw[1]
  x=[]
  y=[]
  c=[]
  
  gain={}
  
  for i in range(N):
    raw = list(input().split(" "))
    x = int(raw[0])
    y = int(raw[1]) % (2*K)
    c = raw[2].strip('\r\n')
    if c == 'W':
      x = x + K
    x = x % (2*K)
    
    if (x,y) in gain:
      gain[(x,y)] = gain[(x,y)] + 1
    else:
      gain[(x,y)] = 1
  
  score = 0
  
  for i in range(2*K):
    for j in range(2*K):
      newscore = 0
      for keys in gain:
        k,l = keys
        if isblack(k-i,l-j,K):
          newscore = newscore + gain[(k,l)]
      score = max(score,newscore)
      
  return score

if __name__ == '__main__':
  
  ans = solve()
  print(ans, flush=True)

Submission status: Time Limit Exceeded

Solution code:
def det(x,K):
  return x % (2*K) in range(K)

def displacedBoard(x,y,board,i,j):
  return board[(x+i,y+j)]

def solve():
  raw = list(map(int,input().split(" ")))
  N = raw[0]
  K = raw[1]
  x=[]
  y=[]
  c=[]
  
  gain={}
  for k in range(2*K):
    for l in range(2*K):
      gain[(k,l)]=0
  
  for i in range(N):
    raw = list(input().split(" "))
    x = int(raw[0])
    y = int(raw[1]) % (2*K)
    c = raw[2].strip('\r\n')
    if c == 'W':
      x = x + K
    x = x % (2*K)
    
    gain[(x,y)] = gain[(x,y)] + 1
  
  board={}
  for k in range(4*K):
    for l in range(4*K):
      board[(k,l)] = (det(k,K) and det(l,K)) or (not (det(k,K) or det(l,K)))

  score = 0
  
  for i in range(2*K):
    for j in range(2*K):
      newscore = 0
      for k in range(2*K):
        for l in range(2*K):
          if displacedBoard(k,l,board,i,j):
            newscore = newscore + gain[(k,l)]
      score = max(score,newscore)

  return score

if __name__ == '__main__':
  
  ans = solve()
  print(ans, flush=True)

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8
from pprint import pprint

line = input().split(" ")
N = int(line[0])
K = int(line[1])
l = []
for _ in range(N):
    line = input().split(" ")
    x = int(line[0])
    y = int(line[1])
    c = line[2]
    if c=="W":
        x += K
    l.append((x%(2*K),y%(2*K),"B"))

def count(x,y):
    # x,y が左下黒だとしていくつ希望を叶えているかカウントする
    ret = 0
    for p in l:
        xx = (p[0]-x+2*K)%(2*K)
        yy = (p[1]-y+2*K)%(2*K)
        if xx<K and yy<K:
            ret += 1
        elif xx>=K and yy>=K:
            ret += 1
    return ret

ret = -1
for x in range(2*K):
    for y in range(2*K):
        t = count(x,y)
        if t>ret:
            ret = t

print(ret)

Submission status: Time Limit Exceeded

Solution code:
import math

N,K = [int(i) for i in input().split()]
X = []
Y = []
C = []
for l in range(N):
    x,y,c = input().split()
    X.append(int(x))
    Y.append(int(y))
    if c == "W":
        C.append(1)
    else:
        C.append(0)

ans = 0
for dx in range(K):
    for dy in range(K):
        a = 0
        for i in range(N):
            if (math.floor((X[i] + dx) / K) % 2 + math.floor((Y[i] + dy) / K) % 2) % 2 == C[i]:
                a = a + 1
        ans = max(ans,max(a, N-a))
        if ans == N:
            break
    if ans == N:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint as pp
import collections
import math

n, k = map(int, input().split())
k2 = k * 2
result = [[0] * k2 for i in range(k2)]
# [x][y] -> sum if fill start x:y

for _ in range(n):
  x, y, c = input().split()
  x = int(x)
  y = int(y)
  if c == 'W':
    y += k
  modx = x % k2
  mody = y % k2
  for xi in range(k):
    for yi in range(k):
      result[(modx + xi) % k2][(mody + yi) % k2] += 1
      result[(modx + xi + k) % k2][(mody + yi + k) % k2] += 1

print(max(max(ary) for ary in result))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, K = list(map(int, input().split()))
x = []
y = []
c = []
for i in range(N):
    xi, yi, ci = list(map(str, input().split()))
    x.append(int(xi))
    y.append(int(yi))
    c.append(ci)


maxFilled = 0
# Bを基準に考える
for i in range(K+1):
    for j in range(K+1):
        cnt = 0
        for idx in range(len(c)):
            h = (x[idx]-i) // K # 水平方向に何番目(0-indexed)のブロックか?
            v = (y[idx]-j) // K # 垂直方向に何番目のブロックか?
            if (v % 2 == 1 and h % 2 == 0 and c[idx] == 'W') or \
               (v % 2 == 0 and h % 2 == 0 and c[idx] == 'B') or \
               (v % 2 == 0 and h % 2 == 1 and c[idx] == 'W') or \
               (v % 2 == 1 and h % 2 == 1 and c[idx] == 'B'):
                cnt += 1
        maxFilled = max(maxFilled, cnt)


print(maxFilled)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
p=[]
for i in range(N):
  x,y,c=input().split()
  p.append([int(x),int(y),c])
res=0
for bx in range(K):
  for by in range(K):
    tmp=0
    for x,y,c in p:
      x=x-bx
      y=y-by
      if(x<0):x=x-(K-1)
      if(y<0):y=y-(K-1)
      x=int( x/K )
      y=int( y/K )
      if (x+y)%2==0 and c=='W':tmp+=1
      elif (x+y)%2==1 and c=='B':tmp+=1
    if res < tmp:res=tmp
    if res < N-tmp:res=N-tmp
print(res)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
favor = []
result = []
def int_or_digit(a):
    if a.isdigit():
        return(int(a))
    else:
        return a
def a(b,t):
    if (0 <= (b % (2*t))) and ((b%(2*t)) <= t-1):
        return 1
    else:
        return 0
for i in range(n):
    favor.append(tuple(map(int_or_digit,input().split())))
#(0,0)~(K-1,K-1)  (1,0)~(K,K-1) ...... (K-1,K-1)~(2K-2,2K-2)
from itertools import product
count = 0
for i,j in product([i for i in range(k)],repeat=2):
        count = 0
        for x,y,c in favor:
            if ((a(x-i,k) + a(y-j,k)) %2 == 0 and c == "W") or ((a(x-i,k) + a(y-j,k)) %2 == 1 and c == "B"):
                count += 1
        result.append(count)
        if count == n:
            print(str(count))
            break
        count = 0
        for x,y,c in favor:
            if ((a(x-i,k) + a(y-j,k)) %2 == 1 and c == "W") or ((a(x-i,k) + a(y-j,k)) %2 == 0 and c == "B"):
                count += 1
        result.append(count)
        if count == n:
            print(str(count))
            break
else:
    print(str(max(result)))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
favor = []
result = []
def int_or_digit(a):
    if a.isdigit():
        return(int(a))
    else:
        return a
def a(b,t):
    if (0 <= (b % (2*t))) and ((b%(2*t)) <= t-1):
        return 1
    else:
        return 0
for i in range(n):
    favor.append(tuple(map(int_or_digit,input().split())))
#(0,0)~(K-1,K-1)  (1,0)~(K,K-1) ...... (K-1,K-1)~(2K-2,2K-2)
from itertools import product
count = 0
for i,j in product([i for i in range(k)],repeat=2):
        count = 0
        for x,y,c in favor:
            if ((a(x-i,k) + a(y-j,k)) %2 == 0 and c == "W") or ((a(x-i,k) + a(y-j,k)) %2 == 1 and c == "B"):
                count += 1
        result.append(count)
        count = 0
        for x,y,c in favor:
            if ((a(x-i,k) + a(y-j,k)) %2 == 1 and c == "W") or ((a(x-i,k) + a(y-j,k)) %2 == 0 and c == "B"):
                count += 1
        result.append(count)
print(str(max(result)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools

def isBlack(K, shift, pos):
    x = shift[0] + pos[0]
    y = shift[1] + pos[1]

    l = int(x/K) + int(y/K)

    return l % 2 == 0

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

desires = []

for i in range(N):
    inp = input().split(" ")
    inp[0] = int(inp[0])
    inp[1] = int(inp[1])
    desires.append(inp)

maxim = 0

for shift in itertools.product(range(K), range(K)):
    count_1 = 0
    count_2 = 0

    for i in range(N):
        isB = isBlack(K, shift, desires[i][:2])

        if isB and desires[i][2] == 'B':
            count_1 += 1
        elif (not isB) and desires[i][2] == 'W':
            count_1 += 1

        if isB and desires[i][2] == 'W':
            count_2 += 1
        elif (not isB) and desires[i][2] == 'B':
            count_2 += 1

        if count_1 + N - i - 1 < maxim and count_2 + N - i - 1 < maxim:
            break

    if maxim < count_1:
        maxim = count_1
    if maxim < count_2:
        maxim = count_2

    if maxim == N:
        break

print(maxim)