Submission #2001920

---

Source Code Expand

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 2005;

int cnt0[N][N],cnt1[N][N];
int n,k;

int calc0(int x1,int x2,int y1,int y2){
	if (x1>x2)return calc0(x1,k*2-1,y1,y2)+calc0(0,x2,y1,y2);
	if (y1>y2)return calc0(x1,x2,y1,k*2-1)+calc0(x1,x2,0,y2);
	return cnt0[x2][y2]-(x1?cnt0[x1-1][y2]:0)-(y1?cnt0[x2][y1-1]:0)+(x1&&y1?cnt0[x1-1][y1-1]:0);
}

int calc0(int x,int y){
	int x1=(x+k-1)%(k*2),y1=(y+k-1)%(k*2);
	return calc0(x,x1,y,y1)+calc0((x1+1)%(k*2),(x+2*k-1)%(2*k),(y1+1)%(k*2),(y+2*k-1)%(2*k));
}

int calc1(int x1,int x2,int y1,int y2){
	if (x1>x2)return calc1(x1,k*2-1,y1,y2)+calc1(0,x2,y1,y2);
	if (y1>y2)return calc1(x1,x2,y1,k*2-1)+calc1(x1,x2,0,y2);
	return cnt1[x2][y2]-(x1?cnt1[x1-1][y2]:0)-(y1?cnt1[x2][y1-1]:0)+(x1&&y1?cnt1[x1-1][y1-1]:0);
}

int calc1(int x,int y){
	int x1=(x+k-1)%(k*2),y1=(y+k-1)%(k*2);
	return calc1(x,x1,y,y1)+calc1((x1+1)%(k*2),(x+2*k-1)%(2*k),(y1+1)%(k*2),(y+2*k-1)%(2*k));
}


int main(){
	n=get(),k=get();
	fo(i,1,n){
		int x=get(),y=get();
		char c;
		c=getchar();
		if (c=='B')cnt0[x%(k*2)][y%(k*2)]++;
		else cnt1[x%(k*2)][y%(k*2)]++;
	}
	fo(i,0,k*2-1)
		fo(j,0,k*2-1){
			if (i)cnt0[i][j]+=cnt0[i-1][j],cnt1[i][j]+=cnt1[i-1][j];
			if (j)cnt0[i][j]+=cnt0[i][j-1],cnt1[i][j]+=cnt1[i][j-1];
			if (i&&j)cnt0[i][j]-=cnt0[i-1][j-1],cnt1[i][j]-=cnt1[i-1][j-1];
		}
	int ans=0;
	fo(i,0,k*2-1)
		fo(j,0,k*2-1){
			int tmp0=calc0(i,j),tmp1=calc1((i+k)%(k*2),j);
			int tmp=tmp0+tmp1;
			ans=max(ans,tmp);
			//if (tmp==6)printf("%d %d\n",i,j);
		}
	printf("%d\n",ans);
	return 0;
}

Submission Info

Judge Result