C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title 動的計画法/2次元累積和 * * verification-helper: IGNORE * verification-helper: PROBLEM https://atcoder.jp/contests/arc089/tasks/arc089_b */ #include <algorithm> #include <iostream> #include "emthrm/dynamic_programming/2d_cumulative_sum.hpp" int main() { int n, k; std::cin >> n >> k; emthrm::CumulativeSum2D<int> black(k * 2, k * 2), white(k * 2, k * 2); while (n--) { int x, y; char c; std::cin >> x >> y >> c; x %= k * 2; y %= k * 2; (c == 'B' ? black : white).add(y, x, 1); } black.build(); white.build(); int ans = 0; for (int i = k - 1; i < k * 2; ++i) { for (int j = k - 1; j < k * 2; ++j) { const int b = black.query(i - k + 1, j - k + 1, i, j) + black.query(0, 0, i - k, j - k) + black.query(0, j + 1, i - k, k * 2 - 1) + black.query(i + 1, 0, k * 2 - 1, j - k) + black.query(i + 1, j + 1, k * 2 - 1, k * 2 - 1); const int w = white.query(0, j - k + 1, i - k, j) + white.query(i - k + 1, 0, i, j - k) + white.query(i - k + 1, j + 1, i, k * 2 - 1) + white.query(i + 1, j - k + 1, k * 2 - 1, j); ans = std::max(ans, b + w); } } for (int i = k - 1; i < k * 2; ++i) { for (int j = k - 1; j < k * 2; ++j) { const int b = black.query(0, j - k + 1, i - k, j) + black.query(i - k + 1, 0, i, j - k) + black.query(i - k + 1, j + 1, i, k * 2 - 1) + black.query(i + 1, j - k + 1, k * 2 - 1, j); const int w = white.query(i - k + 1, j - k + 1, i, j) + white.query(0, 0, i - k, j - k) + white.query(0, j + 1, i - k, k * 2 - 1) + white.query(i + 1, 0, k * 2 - 1, j - k) + white.query(i + 1, j + 1, k * 2 - 1, k * 2 - 1); ans = std::max(ans, b + w); } } std::cout << ans << '\n'; return 0; }
#line 1 "test/dynamic_programming/2d_cumulative_sum.test.cpp" /* * @title 動的計画法/2次元累積和 * * verification-helper: IGNORE * verification-helper: PROBLEM https://atcoder.jp/contests/arc089/tasks/arc089_b */ #include <algorithm> #include <iostream> #line 1 "include/emthrm/dynamic_programming/2d_cumulative_sum.hpp" #line 5 "include/emthrm/dynamic_programming/2d_cumulative_sum.hpp" #include <cassert> #include <iterator> #include <numeric> #include <vector> namespace emthrm { template <typename T> struct CumulativeSum2D { explicit CumulativeSum2D(const int h, const int w) : CumulativeSum2D(std::vector<std::vector<T>>(h, std::vector<T>(w, 0))) {} template <typename U> explicit CumulativeSum2D(const std::vector<std::vector<U>>& a) : is_built(false), h(a.size()), w(a.front().size()), data(h + 1, std::vector<T>(w + 1, 0)) { for (int i = 0; i < h; ++i) { std::copy(a[i].begin(), a[i].end(), std::next(data[i + 1].begin())); } } void add(const int y, const int x, const T val) { assert(!is_built); data[y + 1][x + 1] += val; } void build() { assert(!is_built); is_built = true; for (int i = 0; i < h; ++i) { std::partial_sum(data[i + 1].begin(), data[i + 1].end(), data[i + 1].begin()); } for (int j = 1; j <= w; ++j) { for (int i = 1; i < h; ++i) { data[i + 1][j] += data[i][j]; } } } T query(const int y1, const int x1, const int y2, const int x2) const { assert(is_built); return y1 > y2 || x1 > x2 ? 0 : data[y2 + 1][x2 + 1] - data[y2 + 1][x1] - data[y1][x2 + 1] + data[y1][x1]; } private: bool is_built; const int h, w; std::vector<std::vector<T>> data; }; } // namespace emthrm #line 12 "test/dynamic_programming/2d_cumulative_sum.test.cpp" int main() { int n, k; std::cin >> n >> k; emthrm::CumulativeSum2D<int> black(k * 2, k * 2), white(k * 2, k * 2); while (n--) { int x, y; char c; std::cin >> x >> y >> c; x %= k * 2; y %= k * 2; (c == 'B' ? black : white).add(y, x, 1); } black.build(); white.build(); int ans = 0; for (int i = k - 1; i < k * 2; ++i) { for (int j = k - 1; j < k * 2; ++j) { const int b = black.query(i - k + 1, j - k + 1, i, j) + black.query(0, 0, i - k, j - k) + black.query(0, j + 1, i - k, k * 2 - 1) + black.query(i + 1, 0, k * 2 - 1, j - k) + black.query(i + 1, j + 1, k * 2 - 1, k * 2 - 1); const int w = white.query(0, j - k + 1, i - k, j) + white.query(i - k + 1, 0, i, j - k) + white.query(i - k + 1, j + 1, i, k * 2 - 1) + white.query(i + 1, j - k + 1, k * 2 - 1, j); ans = std::max(ans, b + w); } } for (int i = k - 1; i < k * 2; ++i) { for (int j = k - 1; j < k * 2; ++j) { const int b = black.query(0, j - k + 1, i - k, j) + black.query(i - k + 1, 0, i, j - k) + black.query(i - k + 1, j + 1, i, k * 2 - 1) + black.query(i + 1, j - k + 1, k * 2 - 1, j); const int w = white.query(i - k + 1, j - k + 1, i, j) + white.query(0, 0, i - k, j - k) + white.query(0, j + 1, i - k, k * 2 - 1) + white.query(i + 1, 0, k * 2 - 1, j - k) + white.query(i + 1, j + 1, k * 2 - 1, k * 2 - 1); ans = std::max(ans, b + w); } } std::cout << ans << '\n'; return 0; }