Submission #2983162
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);
chmax(ans, n-tmp);
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Checker |
User |
ferin_tech |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
2493 Byte |
Status |
AC |
Exec Time |
106 ms |
Memory |
94336 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
500 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_000.txt, 0_001.txt, 0_002.txt |
All |
0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt |
Case Name |
Status |
Exec Time |
Memory |
0_000.txt |
AC |
1 ms |
256 KB |
0_001.txt |
AC |
73 ms |
94336 KB |
0_002.txt |
AC |
1 ms |
256 KB |
1_003.txt |
AC |
73 ms |
94336 KB |
1_004.txt |
AC |
1 ms |
256 KB |
1_005.txt |
AC |
1 ms |
256 KB |
1_006.txt |
AC |
1 ms |
256 KB |
1_007.txt |
AC |
2 ms |
3712 KB |
1_008.txt |
AC |
73 ms |
94336 KB |
1_009.txt |
AC |
1 ms |
256 KB |
1_010.txt |
AC |
1 ms |
256 KB |
1_011.txt |
AC |
1 ms |
256 KB |
1_012.txt |
AC |
3 ms |
3712 KB |
1_013.txt |
AC |
74 ms |
94336 KB |
1_014.txt |
AC |
26 ms |
256 KB |
1_015.txt |
AC |
26 ms |
256 KB |
1_016.txt |
AC |
26 ms |
256 KB |
1_017.txt |
AC |
28 ms |
3712 KB |
1_018.txt |
AC |
106 ms |
94336 KB |
1_019.txt |
AC |
4 ms |
3712 KB |
1_020.txt |
AC |
5 ms |
3712 KB |
1_021.txt |
AC |
4 ms |
3712 KB |
1_022.txt |
AC |
4 ms |
3712 KB |
1_023.txt |
AC |
4 ms |
3712 KB |
1_024.txt |
AC |
4 ms |
3712 KB |
1_025.txt |
AC |
22 ms |
384 KB |
1_026.txt |
AC |
96 ms |
94336 KB |
1_027.txt |
AC |
22 ms |
384 KB |
1_028.txt |
AC |
96 ms |
94336 KB |
1_029.txt |
AC |
22 ms |
384 KB |
1_030.txt |
AC |
94 ms |
94336 KB |