Submission #2983152

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll INF = (1LL<<60);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

const int maxh = 2010, maxw = 2010;
int csum[maxh][maxw];
void init(VVI vec) {
  assert(vec.size());
  REP(i, vec.size()) REP(j, vec[0].size()) {
    if(!i && !j) csum[i][j] = vec[i][j];
    else if(!i) csum[i][j] = csum[i][j-1] + vec[i][j];
    else if(!j) csum[i][j] = csum[i-1][j] + vec[i][j];
    else csum[i][j] = csum[i-1][j] + csum[i][j-1] - csum[i-1][j-1] + vec[i][j];
  }
}
// 閉区間, 0-indexedで矩形範囲の合計
int cumsum(int sx, int sy, int gx, int gy) {
  if(!sx && !sy) return csum[gy][gx];
  if(!sx) return csum[gy][gx] - csum[sy-1][gx];
  if(!sy) return csum[gy][gx] - csum[gy][sx-1];
  return csum[gy][gx] - csum[gy][sx-1] - csum[sy-1][gx] + csum[sy-1][sx-1];
}

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

  int n, k;
  cin >> n >> k;
  VVI v(2*k, VI(2*k));
  REP(i, n) {
    int x, y;
    char c;
    cin >> x >> y >> c;
    if(c == 'B') y += k;
    x %= 2*k;
    y %= 2*k;
    v[y][x]++;
  }

  init(v);

  int ans = 0;
  REP(l, k+1) REP(u, k+1) {
    int r = l+k-1, d = u+k-1;
    int tmp = 0;
    if(l!=0 && u!=0) tmp += cumsum(0, 0, l-1, u-1);
    if(l!=0 && d!=2*k-1) tmp += cumsum(0, d+1, l-1, 2*k-1);
    if(r!=2*k-1 && u!=0) tmp += cumsum(r+1, 0, 2*k-1, u-1);
    if(r!=2*k-1 && d!=2*k-1) tmp += cumsum(r+1, d+1, 2*k-1, 2*k-1);
    tmp += cumsum(l, u, r, d);
    chmax(ans, tmp);
  }
  cout << ans << endl;

  return 0;
}

Submission Info

Judge Result