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: Accepted

Solution code:
from operator import sub

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

numA = [[0] * K for i in range(K)]
numB = [[0] * K for i in range(K)]

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

    if c == 'B':
        if (x // K == 0 and y // K == 0) or (x // K == 1 and y // K == 1):
            numA[x % K][y % K] += 1
        else:
            numB[x % K][y % K] += 1
    else:
        if (x // K == 1 and y // K == 0) or (x // K == 0 and y // K == 1):
            numA[x % K][y % K] += 1
        else:
            numB[x % K][y % K] += 1


sumXA = list(map(sum, numA))
sumYA = list(map(sum, zip(*numA)))

sumXB = list(map(sum, numB))
sumYB = list(map(sum, zip(*numB)))

sumA = sum(sumXA)
sumB = sum(sumXB)

Arr = [[0] * K for i in range(K)]
numOKA = sumA
numOKB = sumB
for x in range(K):

    tempOKA = numOKA
    tempOKB = numOKB
    for y in range(K):
        Arr[x][y] = max(tempOKA + sumB - tempOKB, sumA - tempOKA + tempOKB)
        tempOKA -= sumYA[y]
        tempOKB -= sumYB[y]

    sumYA = list(map(sub, sumYA, numA[x]))
    sumYA = list(map(sub, sumYA, numA[x]))
    numOKA -= sumXA[x]

    sumYB = list(map(sub, sumYB, numB[x]))
    sumYB = list(map(sub, sumYB, numB[x]))
    numOKB -= sumXB[x]

print(max(map(max, Arr)))

Submission status: Accepted

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 = [list(accumulate(req)) for req in req_b]
req_w = [list(accumulate(req)) for req in req_w]
req_b = [list(accumulate(req)) for req in zip(*req_b)]
req_w = [list(accumulate(req)) for req in zip(*req_w)]

ans = 0
kb, kw = req_b[-1], req_w[-1]
for dx_b, dx_w in zip(req_b, req_w):
    dxk_b = dx_b[-1]
    dxk_w = dx_w[-1]
    for b1, w1, kyb, kyw in zip(dx_b, dx_w, kb, kw):
        b = bc - kyb - dxk_b + b1 * 2
        w = wc - kyw - dxk_w + w1 * 2
        a = b + wc - w
        ans = max(ans, a, n - a)
print(ans)

Submission status: Accepted

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 = [list(accumulate(req)) for req in req_b]
req_w = [list(accumulate(req)) for req in req_w]
req_b = [list(accumulate(req)) for req in zip(*req_b)]
req_w = [list(accumulate(req)) for req in zip(*req_w)]

ans = 0
kb, kw = req_b[-1], req_w[-1]
for dx, (dx_b, dx_w) in enumerate(zip(req_b, req_w)):
    dxk_b = dx_b[-1]
    dxk_w = dx_w[-1]
    for b1, w1, kyb, kyw in zip(dx_b, dx_w, kb, kw):
        b = bc - kyb - dxk_b + b1 * 2
        w = wc - kyw - dxk_w + w1 * 2
        a = b + wc - w
        ans = max(ans, a, n - a)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import accumulate
def inpl(): return tuple(map(int, input().split()))
N, K = inpl()
P = [[0 for _ in range(2*K)] for _ in range(K)]

for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c=="W":
        y += K
    x, y = x%(2*K), y%(2*K)
    if x >= K:
        if y < K:
            x -= K
            y += K
        else:
            x -= K
            y -= K
    
    P[0][y] += 1
    if x == K-1:
        if y == K-1:
            pass
        elif y > K-1:
            P[0][y-K] -= 1
        elif y < K-1:
            P[0][-1] += 1
            P[0][y+K] -= 1
    else:
        if y == K-1:
            P[x+1][-1] += 1
            P[x+1][y] -= 2
        elif y == 2*K-1:
            P[x+1][y-K] += 2
            P[x+1][y] -= 1
            P[0][y-K] -= 1
        elif y > K-1:
            P[x+1][-1] += 1
            P[x+1][y-K] += 2
            P[x+1][y] -= 2
            P[0][y-K] -= 1
        elif y < K-1:
            P[0][-1] += 1
            P[x+1][y+K] += 2
            P[x+1][-1] -= 1
            P[0][y+K] -= 1
            P[x+1][y] -= 2

S1 = [list(accumulate(l)) for l in zip(*P)]
S2 = [max(list(accumulate(l[::-1]))) for l in zip(*S1)]

print(max(S2))

Submission status: Accepted

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

import numpy as np
blacks = np.zeros((2*K,2*K), dtype=int)

offset = 0

for _ in range(N):
  x,y,c = input().split()
  x,y = int(x),int(y)
  x %= 2*K
  y %= 2*K
  if c == 'B':
    blacks[x,y] += 1
  else:
    blacks[x,y] -= 1
    offset += 1

m = np.zeros((3*K,2*K),dtype=int)
m[:2*K,:] = blacks
m[2*K:,:] = blacks[:K,:]

np.cumsum(m,axis=0, out=m)

m = m[K:,:] - m[:2*K,:]

n = np.zeros((2*K,3*K),dtype=int)
n[:,:2*K] = m
n[:,2*K:] = m[:,:K]

np.cumsum(n,axis=1, out=n)
n = n[:,K:] - n[:,:2*K]

m = np.zeros((3*K,3*K),dtype=int)
m[:2*K,:2*K] = n
m[2*K:,:2*K] = n[:K,:]
m[:2*K,2*K:] = n[:,:K]
m[2*K:,2*K:] = n[:K,:K]

m = m[:2*K,:2*K] + m[K:,K:]
m = m.max()

print(m+offset)

Submission status: Runtime Error

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)]
ruisekiwa=[[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: Runtime Error

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:
        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: Runtime Error

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: Runtime Error

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)

class Ruiwa():
    def __init__(self, a):
        self.H = h = len(a)
        self.W = w = len(a[0])
        self.R = r = a
        for i in range(h):
            for j in range(1,w):
                r[i][j] += r[i][j-1]

        for i in range(1,h):
            for j in range(w):
                r[i][j] += r[i-1][j]

    def search(self, x1, y1, x2, y2):
        if x1 > x2 or y1 > y2:
            return 0

        r = self.R
        rr = r[y2][x2]
        if x1 > 0 and y1 > 0:
            return rr - r[y1-1][x2] - r[y2][x1-1] + r[y1-1][x1-1]
        if x1 > 0:
            rr -= r[y2][x1-1]
        if y1 > 0:
            rr -= r[y1-1][x2]

        return rr

def main():
    n,k = LI()
    a = [LS() for _ in range(n)]
    k2 = k*2
    k4 = k*4
    t = [[0] * (k4) for _ in range(k4)]
    for xs,ys,c in a:
        x = int(xs)
        y = int(ys)
        if c == 'W':
            x += k
        px = x%k2
        py = y%k2
        t[px][py] += 1
        t[px+k][py+k] += 1
        t[px][py+k] -= 1
        t[px+k][py] -= 1

        px += k
        py += k
        t[px][py] += 1
        t[px+k][py+k] += 1
        t[px][py+k] -= 1
        t[px+k][py] -= 1

        px += k
        py -= k
        t[px][py] += 1
        t[px+k][py+k] += 1
        t[px][py+k] -= 1
        t[px+k][py] -= 1

        px -= k2
        py += k2
        t[px][py] += 1
        t[px+k][py+k] += 1
        t[px][py+k] -= 1
        t[px+k][py] -= 1


    rui = Ruiwa(t)

    return max(map(max,rui.R))


print(main())

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
//#include <math.h>
using namespace std;

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> PP;

//-----------------------------------------------------------------------------

int n,k,x,y;
char c;
int imos[5010][5010];

int calc(int y,int x) {
	int res=0;
	if(y>=0&&x>=0) res=imos[min(k*2-1,y)][min(k*2-1,x)];
	return res;
}

int sum(int y,int x) {
	return calc(y,x)-calc(y-k,x)-calc(y,x-k)+calc(y-k,x-k);
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin>>n>>k;
	REP(i,n) {
		cin>>x>>y>>c;
		if(c=='W') x+=k;
		int nx=x%(2*k),ny=y%(2*k);
		imos[ny][nx]++;
	}
	REP(i,k*2) REP(j,k*2) imos[i][j]+=calc(i-1,j);
	REP(i,k*2) REP(j,k*2) imos[i][j]+=calc(i,j-1);
	/*cout<<endl;
	REP(i,k*2) {
		REP(j,k*2) cout<<imos[i][j]<<' ';
		cout<<endl;
	}*/
	int ans=0;
	REP(i,k*2) {
		REP(j,k*2) {
			ans=max(ans,sum(i,j)+sum(i-k,j-k)+sum(i-k,j+k)+sum(i+k,j-k)+sum(i+k,j+k)+sum(i+2*k,j)+sum(i,j+k*2));
		}
	}
	cout<<ans<<endl;

	return 0;
}

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split()) 
KK = 2*K
whites = [[0 for i in range(KK)] for j in range(K)]
total = [[0 for i in range(KK)] for j in range(K)]

for i in range(N):
	x,y,c = input().split()
	x,y = int(x), int(y)
	if c == 'B':
		y += K
	xx = x % K
	yy = y % KK
	whites[xx][yy] += 1

ans = 0
for y in range(K):
	tmp = sum(whites[0][y:y+K]) + sum(whites[1][y:y+K]) + sum(whites[2][y:y+K])
	if ans < tmp:
		ans = tmp
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import heapq
import math
import sys

def hanten(c):
    if c == 'B':
        return 'W'
    else:
        return 'B'

tmp = input()
N, K = [int(a) for a in tmp.split()]
all_num = {'B': 0, 'W': 0}
requirements = [[0 for x in range(K)] for y in range(K)]
for n in range(N):
    tmp = input()
    x, y, c = [a for a in tmp.split()]
    x, y = int(x), int(y)
    x %= (K*2)
    y %= (K*2)
    x_pole = x // K
    y_pole = y // K
    assert x_pole <= 1 and y_pole <= 1
    if x_pole + y_pole == 1:
        c = hanten(c)
    requirements[x % K][y % K] += (1 if c == 'B' else -1)
    all_num[c] += 1

Colors = ['B', 'W']
max_ret = 0
for now_c in Colors:
    num = all_num[now_c]
    direction = 1 if now_c == 'W' else -1
    max_ret = max([max_ret, num])
    bx, ex = 0, K-1
    by, ey = 0, K-1
    while bx <= ex and by <= ey:
        # left ->
        ltor = sum([requirements[bx][y] for y in range(by, ey+1)]) * direction
        # right <-
        # rtol = sum([requirements[ex][y] for y in range(by, ey+1)]) * direction
        # top shita
        ttob = sum([requirements[x][by] for x in range(bx, ex+1)]) * direction
        # bottom ue
        # btot = sum([requirements[x][ey] for x in range(bx, ex+1)]) * direction
        results = [ltor, ttob]
        max_effective = max(results)
        if max_effective == ltor:
            bx += 1
        else:
            by -= 1
        num += max_effective
        max_ret = max([max_ret, num])
print(max_ret)