Submission #3004542
Source Code Expand
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
#include <random>
#include <unordered_map>
#include <unordered_set>
//#include <opencv2/core.hpp>
//#include <opencv2/highgui.hpp>
//#include <opencv2/imgproc.hpp>
using namespace std;
//呪文
#define DUMPOUT cerr
#define dump(...) DUMPOUT<<" ";DUMPOUT<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl;DUMPOUT<<" ";dump_func(__VA_ARGS__)
typedef unsigned uint; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; typedef pair<string, string> pss;
template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const pair<_KTy, _Ty>& m) { ostr << "{" << m.first << ", " << m.second << "}"; return ostr; }
template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const map<_KTy, _Ty>& m) { if (m.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { ostr << ", " << *itr; } ostr << "}"; return ostr; }
template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const unordered_map<_KTy, _Ty>& m) { if (m.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { ostr << ", " << *itr; } ostr << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const vector<_Ty>& v) { if (v.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { ostr << ", " << *itr; } ostr << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const set<_Ty>& s) { if (s.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { ostr << ", " << *itr; } ostr << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const unordered_set<_Ty>& s) { if (s.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { ostr << ", " << *itr; } ostr << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const stack<_Ty>& s) { if (s.empty()) { ostr << "{ }"; return ostr; } stack<_Ty> t(s); ostr << "{" << t.top(); t.pop(); while (!t.empty()) { ostr << ", " << t.top(); t.pop(); } ostr << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const list<_Ty>& l) { if (l.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << l.front(); for (auto itr = ++l.begin(); itr != l.end(); ++itr) { ostr << ", " << *itr; } ostr << "}"; return ostr; }
template <typename _KTy, typename _Ty> istream& operator >> (istream& istr, pair<_KTy, _Ty>& m) { istr >> m.first >> m.second; return istr; }
template <typename _Ty> istream& operator >> (istream& istr, vector<_Ty>& v) { for (size_t i = 0; i < v.size(); i++) istr >> v[i]; return istr; }
namespace aux { // print tuple
template<typename Ty, unsigned N, unsigned L> struct tp { static void print(ostream& os, const Ty& v) { os << get<N>(v) << ", "; tp<Ty, N + 1, L>::print(os, v); } };
template<typename Ty, unsigned N> struct tp<Ty, N, N> { static void print(ostream& os, const Ty& value) { os << get<N>(value); } };
}
template<typename... Tys> ostream& operator<<(ostream& os, const tuple<Tys...>& t) { os << "{"; aux::tp<tuple<Tys...>, 0, sizeof...(Tys)-1>::print(os, t); os << "}"; return os; }
template<typename A, size_t N, typename T> inline void Fill(A(&array)[N], const T &val) { std::fill((T*)array, (T*)(array + N), val); }
void dump_func() { DUMPOUT << endl; }
template <class Head, class... Tail> void dump_func(Head&& head, Tail&&... tail) { DUMPOUT << head; if (sizeof...(Tail) == 0) { DUMPOUT << " "; } else { DUMPOUT << ", "; } dump_func(std::move(tail)...); }
#define PI 3.14159265358979323846
#define EPS 1e-10
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define all(j) (j).begin(), (j).end()
#define SZ(j) ((int)(j).size())
#define fake false
// [i1, i2], [j1, j2]
int sum2D(const vector<vector<int>>& sum, int i1, int j1, int i2, int j2) {
if (i1 == 0 && j1 == 0)
return sum[i2][j2];
if (i1 == 0)
return sum[i2][j2] - sum[i2][j1 - 1];
if (j1 == 0)
return sum[i2][j2] - sum[i1 - 1][j2];
return sum[i2][j2] - sum[i2][j1 - 1] - sum[i1 - 1][j2] + sum[i1 - 1][j1 - 1];
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int N, K;
cin >> N >> K;
vector<int> x(N), y(N);
vector<char> c(N);
for (int i = 0; i < N; i++) {
cin >> x[i] >> y[i] >> c[i];
x[i] %= 2 * K; y[i] %= 2 * K;
}
vector<vector<int>> black(2 * K + 1, vector<int>(2 * K + 1, 0));
vector<vector<int>> white(2 * K + 1, vector<int>(2 * K + 1, 0));
for (int i = 0; i < N; i++) {
if (c[i] == 'B')
black[y[i]][x[i]]++;
else
white[y[i]][x[i]]++;
}
for (int i = 0; i < 2 * K; i++) {
for (int j = 0; j < 2 * K; j++) {
black[i][j + 1] += black[i][j];
white[i][j + 1] += white[i][j];
}
}
for (int j = 0; j <= 2 * K; j++) {
for (int i = 0; i < 2 * K; i++) {
black[i + 1][j] += black[i][j];
white[i + 1][j] += white[i][j];
}
}
int ans = 0;
for (int h = 0; h < K; h++) {
for (int w = 0; w < K; w++) {
// 2K * 2K 領域の左下が黒
int ok = 0;
ok += sum2D(black, 0, 0, K - h - 1, K - w - 1);
ok += sum2D(black, 2 * K - h, 0, 2 * K - 1, K - w - 1);
ok += sum2D(black, K - h, K - w, 2 * K - h - 1, 2 * K - w - 1);
ok += sum2D(black, 0, 2 * K - w, K - h - 1, 2 * K - 1);
ok += sum2D(black, 2 * K - h, 2 * K - w, 2 * K - 1, 2 * K - 1);
ok += sum2D(white, 0, K - w, K - h - 1, 2 * K - w - 1);
ok += sum2D(white, K - h, 0, 2 * K - h - 1, K - w - 1);
ok += sum2D(white, 2 * K - h, K - w, 2 * K - 1, 2 * K - w - 1);
ok += sum2D(white, K - h, 2 * K - w, 2 * K - h - 1, 2 * K - 1);
ans = max(ans, ok);
// 2K * 2K 領域の左下が白
ok = 0;
ok += sum2D(white, 0, 0, K - h - 1, K - w - 1);
ok += sum2D(white, 2 * K - h, 0, 2 * K - 1, K - w - 1);
ok += sum2D(white, K - h, K - w, 2 * K - h - 1, 2 * K - w - 1);
ok += sum2D(white, 0, 2 * K - w, K - h - 1, 2 * K - 1);
ok += sum2D(white, 2 * K - h, 2 * K - w, 2 * K - 1, 2 * K - 1);
ok += sum2D(black, 0, K - w, K - h - 1, 2 * K - w - 1);
ok += sum2D(black, K - h, 0, 2 * K - h - 1, K - w - 1);
ok += sum2D(black, 2 * K - h, K - w, 2 * K - 1, 2 * K - w - 1);
ok += sum2D(black, K - h, 2 * K - w, 2 * K - h - 1, 2 * K - 1);
ans = max(ans, ok);
}
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Checker |
User |
komori3 |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
6697 Byte |
Status |
AC |
Exec Time |
238 ms |
Memory |
32640 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 |
212 ms |
31744 KB |
0_002.txt |
AC |
1 ms |
256 KB |
1_003.txt |
AC |
212 ms |
31744 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 |
640 KB |
1_008.txt |
AC |
212 ms |
31744 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 |
2 ms |
640 KB |
1_013.txt |
AC |
212 ms |
31744 KB |
1_014.txt |
AC |
23 ms |
1152 KB |
1_015.txt |
AC |
23 ms |
1152 KB |
1_016.txt |
AC |
23 ms |
1152 KB |
1_017.txt |
AC |
24 ms |
1536 KB |
1_018.txt |
AC |
238 ms |
32640 KB |
1_019.txt |
AC |
3 ms |
640 KB |
1_020.txt |
AC |
3 ms |
640 KB |
1_021.txt |
AC |
4 ms |
640 KB |
1_022.txt |
AC |
3 ms |
640 KB |
1_023.txt |
AC |
3 ms |
640 KB |
1_024.txt |
AC |
3 ms |
640 KB |
1_025.txt |
AC |
19 ms |
1152 KB |
1_026.txt |
AC |
232 ms |
32512 KB |
1_027.txt |
AC |
19 ms |
1152 KB |
1_028.txt |
AC |
231 ms |
32512 KB |
1_029.txt |
AC |
19 ms |
1152 KB |
1_030.txt |
AC |
231 ms |
32512 KB |