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:
from itertools import accumulate
from operator import add

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

# Gss[i][j]: 「市松模様の黒い部分の右上のマス」が(i,j)のとき、満たせる要望の個数
Gss = [[0] * K2 for i in range(K2)]

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

    # 要望を「0<=x<2K, 0<=y<K, 'B'」に変換する
    if c == 'W':
        x -= K
    x, y = x % K2, y % K2

    if y >= K:
        x, y = (x - K) % K2, y - K

    # 要望を満たす「市松模様の黒い部分の右上のマス」に対して、+1する
    # （後で累積和を取る）
    Gss[x][y] += 1
    Gss[x][y - K] += -1
    if x != K:
        Gss[x - K][y - K] += 1
        Gss[x - K][y] += -1
    if x > K:
        Gss[0][y] += 1
        Gss[0][y - K] += -1

# 累積和を取る
Gss = [list(accumulate(Gs)) for Gs in Gss]
Gss = [list(accumulate(Gs)) for Gs in zip(*Gss)]
Gss = list(map(list, zip(*Gss))) # 転置

# 「K<=y<2K」の部分を、「0<=y<K」に重ね合わせる
Gss = [list(map(add, Gss[i][:K], Gss[i - K][K:])) for i in range(K2)]

# Gssの最大値が答え
print(max(map(max, Gss)))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
x=[0 for i in range(N)]
y=[0 for i in range(N)]
for i in range(N):
    a,b,c=map(str,input().split())
    a=int(a)
    b=int(b)
    if c=="W":
        b+=K
    x[i]=a%(2*K)
    y[i]=b%(2*K)
board=[[0 for i in range(2*K+1)] for i in range(2*K+1)]
for i in range(N):
    if x[i]>=K and y[i]>=K:
        x[i]-=K
        y[i]-=K
    if x[i]<K and y[i]>=K:
        x[i]+=K
        y[i]-=K
    if x[i]>=K and y[i]<K:
        board[0][y[i]+1]+=1
        board[0][y[i]+K+1]-=1
        board[x[i]-K+1][y[i]+1]-=2
        board[x[i]-K+1][y[i]+K+1]+=2
        board[x[i]-K+1][0]+=1
        board[x[i]+1][0]-=1
        board[x[i]+1][y[i]+1]+=2
        board[x[i]+1][y[i]+K+1]-=2
    if x[i]<K and y[i]<K:
        board[x[i]+1][y[i]+1]+=2
        board[x[i]+K+1][y[i]+K+1]+=2
        board[x[i]+1][y[i]+K+1]-=2
        board[x[i]+K+1][y[i]+1]-=2
        board[0][0]+=1
        board[x[i]+1][0]-=1
        board[0][y[i]+1]-=1
        board[x[i]+K+1][0]+=1
        board[0][y[i]+K+1]+=1
tmp=[[0 for i in range(2*K)] for i in range(2*K)]
bs=[[0 for i in range(2*K)] for i in range(2*K)]
for i in range(2*K):
    for j in range(2*K):
        if i==0:
            tmp[i][j]=board[i][j]
        else:
            tmp[i][j]=board[i][j]+tmp[i-1][j]
for i in range(2*K):
    for j in range(2*K):
        if j==0:
            bs[i][j]=tmp[i][j]
        else:
            bs[i][j]=tmp[i][j]+bs[i][j-1]
ans=bs[0][0]
for i in range(2*K):
    for j in range(2*K):
        if bs[i][j]>ans:
            ans=bs[i][j]
print(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().strip()


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):
    K2 = 2*K
    ans = [[0] * (K2+K2) for _j in range(K2+K2)]
    XY = list(
        map(lambda x:
            (x[0] % K2, (x[1] if x[2] == 'W' else x[1] + K) % K2), XYC
            )
    )

    for x, y in XY:
        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+2*K][y+K] -= 1
        ans[x+K][y+2*K] -= 1
        ans[x+2*K][y+2*K] += 1

    for i in range(K2+K2):
        for j in range(1, K2+K2):
            ans[i][j] += ans[i][j-1]
    for i in range(1, K2+K2):
        for j in range(K2+K2):
            ans[i][j] += ans[i-1][j]

    ans_ = [[0] * K2 for _j in range(K2)]
    for i in range(K2+K2):
        for j in range(K2+K2):
            ans_[i % K2][j % K2] += ans[i][j]

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

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

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

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

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

    return ans

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]

def printm(m):
        return
        #print "["
        for r in m:
                print " ", r
        #print "]"
        print

N, K = rdi()
X = []
Y = []
C = []
for i in range(N):
        x, y, c = rd().split()
        X.append(int(x))
        Y.append(int(y))
        C.append(c == 'W')

bm = [ [ 0 ] * K for i in range(K) ]
wm = [ [ 0 ] * K for i in range(K) ]

for i in range(N):
        x = X[i] % (2 * K)
        y = Y[i] % (2 * K)
        if x < K and y < K or x >= K and y >= K:
                if C[i]:
                        wm[y % K][x % K] += 1
                else:
                        bm[y % K][x % K] += 1
        else:
                if C[i]:
                        bm[y % K][x % K] += 1
                else:
                        wm[y % K][x % K] += 1

printm(bm)
printm(wm)

sbm1 = [ [ 0 ] * (K+3) for i in range(K+3) ]
sbm2 = [ [ 0 ] * (K+3) for i in range(K+3) ]
sbm3 = [ [ 0 ] * (K+3) for i in range(K+3) ]
sbm4 = [ [ 0 ] * (K+3) for i in range(K+3) ]
swm1 = [ [ 0 ] * (K+3) for i in range(K+3) ]
swm2 = [ [ 0 ] * (K+3) for i in range(K+3) ]
swm3 = [ [ 0 ] * (K+3) for i in range(K+3) ]
swm4 = [ [ 0 ] * (K+3) for i in range(K+3) ]

for i in range(K):
        for j in range(K):
                sbm1[i+1][j+1] = sbm1[i+1][j] + sbm1[i][j+1] - sbm1[i][j] + bm[i][j]
                swm1[i+1][j+1] = swm1[i+1][j] + swm1[i][j+1] - swm1[i][j] + wm[i][j]
                sbm2[i+1][K-j] = sbm2[i+1][K-j+1] + sbm2[i][K-j] - sbm2[i][K-j+1] + bm[i][K-1-j]
                swm2[i+1][K-j] = swm2[i+1][K-j+1] + swm2[i][K-j] - swm2[i][K-j+1] + wm[i][K-1-j]
                sbm3[K-i][j+1] = sbm3[K-i][j] + sbm3[K-i+1][j+1] - sbm3[K-i+1][j] + bm[K-1-i][j]
                swm3[K-i][j+1] = swm3[K-i][j] + swm3[K-i+1][j+1] - swm3[K-i+1][j] + wm[K-1-i][j]
                sbm4[K-i][K-j] = sbm4[K-i][K-j+1] + sbm4[K-i+1][K-j] - sbm4[K-i+1][K-j+1] + bm[K-1-i][K-1-j]
                swm4[K-i][K-j] = swm4[K-i][K-j+1] + swm4[K-i+1][K-j] - swm4[K-i+1][K-j+1] + wm[K-1-i][K-1-j]

printm(sbm1)
printm(sbm2)
printm(sbm3)
printm(sbm4)
printm(swm1)
printm(swm2)
printm(swm3)
printm(swm4)

s = 0
tm = [ [ None ] * (K+1) for i in range(K+1) ]
for i in range(K+1):
        for j in range(K+1):
                s1 = sbm1[i+1][j+1] + sbm4[i+2][j+2] + swm2[i+1][j+2] + swm3[i+2][j+1]
                s2 = swm1[i+1][j+1] + swm4[i+2][j+2] + sbm2[i+1][j+2] + sbm3[i+2][j+1]
                s = max(s, s1, s2)
                tm[i][j] = (s1, s2)

printm(tm)

print s

Submission status: Time Limit Exceeded

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

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
class st:
	def __init__(self,n):
		self.a=[[0]*n for i in range(n)]
		self.n=n
	def add(self,i,j,k):
		self.a[i][j]+=k
	def build(self):
		for i in range(self.n):
			for j in range(1,self.n):
				self.a[i][j]+=self.a[i][j-1]
			if (i):
				for j in range(self.n):
					self.a[i][j]+=self.a[i-1][j]
	def qry1(self,i,j):
		if (i<0 or j<0): return 0
		return self.a[i][j]
	def qry(self,i1,j1,i2,j2):
		if (i2<0 or j2<0): return 0
		if (i1>=self.n or j1>=self.n): return 0
		i1=max(i1,0)
		j1=max(j1,0)
		i2=min(i2,self.n-1)
		j2=min(j2,self.n-1)
		return self.qry1(i2,j2)-self.qry1(i1-1,j2)-self.qry1(i2,j1-1)+self.qry1(i1-1,j1-1)
def main():
	n,k=map(int,input().split())
	x=[0]*n
	y=[0]*n
	c=['']*n
	cnt=0
	for i in range(n):
		tmp=input().split()
		x[i]=int(tmp[0])
		x[i]%=k*2
		y[i]=int(tmp[1])
		y[i]%=k*2
		c[i]=tmp[2]
		if (c[i]=='B'): cnt+=1
	a=st(k*2)
	for i in range(n):
		if (c[i]=='B'): a.add(x[i],y[i],-1)
		else: a.add(x[i],y[i],1)
	a.build()
	ans=0
	for i in range(k*2):
		for j in range(k*2):
			tmp=0
			for di in range(-2,3):
				for dj in range(-2,3):
					if ((di+dj)%2): continue
					ni=i+di*k
					nj=j+dj*k
					tmp+=a.qry(ni,nj,ni+k-1,nj+k-1)
			ans=max(ans,cnt+tmp)
	print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def calc(K, xyc):
    K2 = K * 2
    N = len(xyc)

    m = defaultdict(int)
    for x, y, c in xyc:
        y += c * K
        x1, y1 = x % K2, y % K2
        x2, y2 = x1 + K, y1 + K
        m[x1, y1] += 1
        m[x2, y2] += 1
        m[x2, y1] -= 1
        m[x1, y2] -= 1
        x1, y1 = (x + K) % K2, (y + K) % K2
        x2, y2 = x1 + K, y1 + K
        m[x1, y1] += 1
        m[x2, y2] += 1
        m[x2, y1] -= 1
        m[x1, y2] -= 1

    ms = [[0] * (K2 + 1) for i in range(K2 + 1)]
    for y in range(0, K2):
        ms0 = ms[y]
        ms1 = ms[y - 1]
        for x in range(0, K2):
            ms0[x] = m[x, y] + ms0[x-1] + ms1[x] - ms1[x-1]
    
    rmax = 0
    for y in range(K, K2):
        for x in range(K, K2):
            rcount = ms[y][x]
            rmax = max(rmax, rcount, N - rcount)

    return rmax

if __name__ == '__main__':
    N, K = [int(e) for e in input().split()]
    xyc = [(int(x), int(y), c == "W") for x, y, c in [input().split() for i in range(N)]]
    print(calc(K, xyc))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def calc(K, xyc):
    K2 = K * 2
    K3 = K * 3
    K4 = K * 4
    xys = [(x % K2, (y + c * K) % K2) for x, y, c in xyc]

    m = defaultdict(int)
    for x, y in xys:
        x1, y1 = x, y
        x2, y2 = (x1 + K), (y1 + K)
        m[x1, y1] += 1
        m[x2, y2] += 1
        m[x1, y2] -= 1
        m[x2, y1] -= 1

        x1, y1 = x, y + K2
        x2, y2 = (x1 + K), (y1 + K)
        m[x1, y1] += 1
        m[x2, y2] += 1
        m[x1, y2] -= 1
        m[x2, y1] -= 1

        x1, y1 = x + K2, y
        x2, y2 = (x1 + K), (y1 + K)
        m[x1, y1] += 1
        m[x2, y2] += 1
        m[x1, y2] -= 1
        m[x2, y1] -= 1

        x1, y1 = x + K2, y + K2
        x2, y2 = (x1 + K), (y1 + K)
        m[x1, y1] += 1
        m[x2, y2] += 1
        m[x1, y2] -= 1
        m[x2, y1] -= 1


    mt = defaultdict(int)
    for y in range(K4):
        for x in range(K4):
            mt[x, y] = m[x, y] + mt[(x - 1), y] + mt[x, (y - 1)] - mt[(x - 1), (y - 1)]

    rmax = 0
    for y in range(K, K3):
        for x in range(K, K3):
            rcount = mt[x + K, y + K] + mt[x, y]
            rmax = max(rmax, rcount)

    return rmax

N, K = [int(e) for e in input().split()]
xyc = [input().split() for i in range(N)]
xyc = [(int(x), int(y), c == "W") for x, y, c in xyc]

print(calc(K, xyc))

Submission status: Time Limit Exceeded

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

xp = [[] for _ in range(K)]
yp = [[] for _ in range(K)]
score = 0
for i in range(N):
  x, y, c = input().split()
  x, y = int(x) % (2*K), int(y) % (2*K)
  c = c == 'W'
  if x >= K:
    c = not c
    x -= K
  if y >= K:
    c = not c
    y -= K
  if c:
    score += 1
  info = (x, y, [-1, 1][c])
  xp[x].append(info)
  yp[y].append(info)

func = [max(abs(x), N-abs(x)) for x in range(N+1)]
ans = func[score]
x = y = 0
sign = 1
while True:
  if x >= K:
    for px, py, pc in yp[y]:
      score += pc * sign
    ans = max(ans, func[score])
    x = 0
    y += 1
    sign = 1 if y % 2 == 0 else -1
    if y >= K:
      break
  else:
    for px, py, pc in xp[x]:
      if py >= y:
        score -= pc * sign
      else:
        score += pc * sign
    ans = max(ans, func[score])
    x += 1

print(ans)

Submission status: Time Limit Exceeded

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

xp = [[] for _ in range(K)]
yp = [[] for _ in range(K)]
score = 0
for i in range(N):
  x, y, c = input().split()
  x, y = int(x) % (2*K), int(y) % (2*K)
  c = c == 'W'
  if x >= K:
    c = not c
    x -= K
  if y >= K:
    c = not c
    y -= K
  if c:
    score += 1
  info = (x, y, [-1, 1][c])
  xp[x].append(info)
  yp[y].append(info)

func = lambda x: max(abs(x), N-abs(x))
ans = func(score)
x = y = 0
sign = 1
while True:
  if x >= K:
    for px, py, pc in yp[y]:
      score += pc * sign
    ans = max(ans, func(score))
    x = 0
    y += 1
    sign = 1 if y % 2 == 0 else -1
    if y >= K:
      break
  else:
    for px, py, pc in xp[x]:
      score += pc * [1, -1][py >= y] * sign
    ans = max(ans, func(score))
    x += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calc0(K, xyc):
    rmax = 0
    for i in range(K * 2):
        for j in range(K * 2):
            rcount = 0
            for x, y, c in xyc:
                rcount += ((x + j) // K + (y + i) // K) % 2 == c
            rmax = max(rmax, rcount)
    return rmax

def calc1(K, xyc):
    rmax = 0
    for i in range(K * 2):
        xs = [(x + c * K + (y + i) // K * K) % (2 * K) for x, y, c in xyc]
        for j in range(K * 2):
            rcount = 0
            for x in xs:
                rcount += ((x + j) // K)  % 2 == 1
            rmax = max(rmax, rcount)
    return rmax

def calc(K, xyc):
    rmax = 0
    for i in range(K):
        ts = [0 for x in range(K * 2)]
        for x, y, c in xyc:
            a = (x + c * K + (y + i) // K * K) % (2 * K)
            ts[a] += 1
        rcount = sum(ts[0:K])
        for j in range(K):
            rcount += -ts[j] + ts[j+K]
            rmax = max(rmax, rcount, N - rcount)
    return rmax

#import random
#N = 10000
#K = 20
#xyc = [(random.randint(0, 10000), random.randint(0, 10000), random.randint(0, 10000) % 2) for i in range(N)]

N, K = [int(e) for e in input().split()]
xyc = [input().split() for i in range(N)]
xyc = [(int(x), int(y), c == "W") for x, y, c in xyc]

#print(calc0(K, xyc))
#print(calc1(K, xyc))
print(calc(K, xyc))

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(e) for e in input().split()]
xyc = [input().split() for i in range(N)]
xyc = [(int(x), int(y), c == "W") for x, y, c in xyc]

def calc0(K, xyc):
    rmax = 0
    for i in range(K * 2):
        for j in range(K * 2):
            rcount = 0
            for x, y, c in xyc:
                rcount += ((x + j) // K + (y + i) // K) % 2 == c
            rmax = max(rmax, rcount)
    return rmax

def calc1(K, xyc):
    rmax = 0
    for i in range(K * 2):
        xs = [(x + c * K + (y + i) // K * K) % (2 * K) for x, y, c in xyc]
        for j in range(K * 2):
            rcount = 0
            for x in xs:
                rcount += ((x + j) // K)  % 2 == 1
            rmax = max(rmax, rcount)
    return rmax

def calc(K, xyc):
    rmax = 0
    for i in range(K):
        xs = [(x + c * K + (y + i) // K * K) % (2 * K) for x, y, c in xyc]
        ts = [0 for x in range(K * 4)]
        for x in xs:
            ts[x] += 1
            ts[x + K * 2] += 1
        rcount = sum(ts[0:K])
        for j in range(K):
            rcount += -ts[j] + ts[j+K]
            rmax = max(rmax, rcount, N - rcount)
    return rmax

#import random
#N = 10000
#K = 1000
#xyc = [(random.randint(0, 10000), random.randint(0, 10000), random.randint(0, 10000) % 2) for i in range(N)]

#print(calc0(K, xyc))
#print(calc1(K, xyc))
print(calc(K, xyc))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.ndimage.interpolation import shift

n,k = map(int, input().split())
order = [input().split() for _ in range(n)]

"""
   +
WWW|BBB
WWW|BBB
WWW|BBB
---0---+
BBB|WWW
BBB|WWW
BBB|WWW

"""

candidate = np.zeros([k,2*k], dtype="int32")

ones  = np.ones([k,k], dtype="int32")
zeros = np.zeros([k,k], dtype="int32")
left  = np.concatenate((ones,zeros), axis=0)
right = np.concatenate((zeros,ones), axis=0)
tile  = np.concatenate((left,right), axis=1)

def feasible(request):
    x = int(request[0])
    y = int(request[1])
    if request[2] == "B":
        x += k
    x = x % (k*2)
    y = y % (k*2)
    
    ichimatsu = tile[:,:]
    ichimatsu = np.roll(ichimatsu, x, axis=1)
    ichimatsu = np.roll(ichimatsu, y, axis=0)
    
    return ichimatsu[:k,:]
    

for desire in order:
    candidate += feasible(desire)
else:
    print(candidate.max())

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))
x = []
y = []
c = []
for i in range(N):
    temp = list(input().split())
    x.append(int(temp[0]))
    y.append(int(temp[1]))
    c.append(temp[2])

xt = []
yt = []
ct = []
score = []
for n in range(N):
    flag = True
    xp = x[n] % (2 * K)
    yp = y[n] % (2 * K)
    for i in range(len(xt)):
        if xt[i] == xp and yt[i] == yp and ct[i] == c[n]:
            flag = False
            idx = i
            break
    if flag:
        xt.append(xp)
        yt.append(yp)
        ct.append(c[n])
        score.append(1)
    else:
        score[idx] += 1
x = xt
y = yt
c = ct

result = 0
flag = True
for i in range(K):
    if flag:
        for j in range(K):
            if flag:
                val = [int((x[n] + i) % (2 * K) / K) + int((
                    y[n] + j) % (2 * K) / K) for n in range(len(x))]
                for k in [['B', 'W'], ['W', 'B']]:
                    count = 0
                    for n in range(len(x)):
                        if val[n] in [0, 2] and c[n] == k[0]:
                            count += score[n]
                        elif val[n] == 1 and c[n] == k[1]:
                            count += score[n]
                    if result < count:
                        result = count
                    if result == N:
                        flag = False
                        break

print(result)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
xyc = []
for i in range(N):
    tmp_x, tmp_y, tmp_c = input().split()
    xyc.append([int(tmp_x), int(tmp_y), tmp_c])

def check(sx, sy, K, x, y):
    x = x % (2*K)
    y = y % (2*K)
    if x < sx or x >= sx + K:
        if y < sy:
            return 'W'
        elif y < sy + K:
            return 'B'
        else:
            return 'W'
    #elif x >= sx and x < sx + K:
    else:
        if y < sy:
            return 'B'
        elif y < sy + K:
            return 'W'
        else:
            return 'B'


ans = 0
for sx in range(K+1):
    for sy in range(K+1):
        r = 0
        for i in range(N):
            if check(sx, sy, K, xyc[i][0], xyc[i][1]) == xyc[i][2]:
                r = r + 1
        ans = max(ans, r)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

n, k = map(int, input().split())
k2 = k * 2
req_b = [[0] * k for _ in range(k)]
req_w = [[0] * k for _ in range(k)]
bc, wc = 0, 0
for i in range(n):
    x, y, c = input().split()
    x, y = int(x), int(y)
    rx, ry = x % k2, y % k2
    b = c == 'B'
    if rx >= k:
        rx -= k
        if ry >= k:
            ry -= k
        else:
            b = not b
    elif ry >= k:
        ry -= k
        b = not b
    if b:
        req_b[rx][ry] += 1
        bc += 1
    else:
        req_w[rx][ry] += 1
        wc += 1

req_b[0] = list(accumulate(req_b[0]))
req_w[0] = list(accumulate(req_w[0]))

for i in range(1, k):
    req_b[i][0] += req_b[i - 1][0]
    req_w[i][0] += req_w[i - 1][0]
    for j in range(1, k):
        req_b[i][j] += req_b[i][j - 1] + req_b[i - 1][j] - req_b[i - 1][j - 1]
        req_w[i][j] += req_w[i][j - 1] + req_w[i - 1][j] - req_w[i - 1][j - 1]

ans = 0
for dx in range(k):
    dxk_b = req_b[dx][-1]
    dxk_w = req_w[dx][-1]
    for dy in range(k):
        b1 = req_b[dx][dy]
        b2 = bc - req_b[k - 1][dy] - dxk_b + b1
        w1 = req_w[dx][dy]
        w2 = wc - req_w[k - 1][dy] - dxk_w + w1
        b, w = b1 + b2, w1 + w2
        ans = max(ans, b + wc - w, w + bc - b)
        # print(dx, dy, b, w, b + wc - w, w + bc - b)
print(ans)

Submission status: Time Limit Exceeded

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

n,k = map(int,raw_input().split())
kibou = []
for i in range(n):
    line = raw_input().split()
    line[0] = int(line[0])
    line[1] = int(line[1])
    if line[2] == "W":
        line[2] = 0
    else:
        line[2] = 1
    kibou.append(line)

max_score = 0
for i in range(k):
    if max_score == n:
        break
    for j in range(k):
        score = 0
        for line in kibou:
            if ((line[0]+i)/k+(line[1]+j)/k)%2 == line[2]:
                score += 1
        max_score = max(score,max_score,(n-score))
        if max_score == n:
            break

print max_score

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
x = []
y = []
c = []
ans = 0
for n in range(N):
    X,Y,C = map(str,input().split())
    x.append(int(X))
    y.append(int(Y))
    c.append(C)

for kx in range(K):
    for ky in range(K):
        num = 0
        for n in range(N):
            if ((x[n]-kx)//K)%2 == 0:
                xb = True
            else:
                xb = False
            if ((y[n]-ky)//K)%2 == 0:
                yb = True
            else:
                yb = False
            if xb == yb and c[n] == 'B':
                num += 1
            elif xb != yb and c[n] == 'W':
                num += 1
        ans = max(ans,max(num,N-num))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))
x = []
y = []
c = []
for i in range(N):
    temp = list(input().split())
    x.append(int(temp[0]))
    y.append(int(temp[1]))
    c.append(temp[2])

# xt = []
# yt = []
# score = []
# for n in range(N):
#     xt.append(x)

result = 0
flag = True
for i in range(K):
    if flag:
        for j in range(K):
            if flag:
                val = [int(((x[n] + i) % (2 * K)) / K) + int(((y[n] + j) % (2 * K)) / K) for n in range(N)]
                for k in [['B', 'W'], ['W', 'B']]:
                    count = 0
                    for n in range(N):
                        if val[n] in [0, 2] and c[n] == k[0]:
                            count += 1
                        elif val[n] == 1 and c[n] == k[1]:
                            count += 1
                    if result < count:
                        result = count
                    # if result == N:
                    #     flag = False
                    #     break

print(result)

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))
x = []
y = []
c = []
for i in range(N):
    temp = list(input().split())
    x.append(int(temp[0]))
    y.append(int(temp[1]))
    c.append(temp[2])

result = 0
flag = True
for i in range(K + 1):
    if flag:
        for j in range(K + 1):
            if flag:
                val = [int(((x[n] + i) % (2 * K)) / K) + int(((y[n] + j) % (2 * K)) / K) for n in range(N)]
                for k in [['B', 'W'], ['W', 'B']]:
                    count = 0
                    for n in range(N):
                        if val[n] in [0, 2] and c[n] == k[0]:
                            count += 1
                        elif val[n] == 1 and c[n] == k[1]:
                            count += 1
                    if result < count:
                        result = count
                    if result == N:
                        flag = False
                        break

print(result)

Submission status: Time Limit Exceeded

Solution code:
#
N, K = list(map(int, input().split()))
X = []
Y = []
C = []
dX = [0]
dY = [0]
for i in range(N):
    x, y, c = input().rstrip().split()
    X.append(int(x))
    Y.append(int(y))
    C.append(c)
    dX.append(K - int(x)%K)
    dY.append(K - int(y)%K)
dX = set(dX)
dY = set(dY)

def color(x, y, dx=0, dy=0):
    if ((x+dx)//K + (y+dy)//K)%2==0:
        return 'W'
    else:
        return 'B'

def count(dx=0, dy=0):
    cnt = 0
    for i in range(N):
        if color(X[i], Y[i], dx, dy)==C[i]:
            cnt += 1
    return cnt
#
cnt = 0
for i in dX:
    for j in dY:
        cnt_ = count(i, j)
        if cnt_==N:
            print(N)
            exit()
        cnt = max(cnt, cnt_)
print(cnt)