cp-library

C++ Library for Competitive Programming

View the Project on GitHub emthrm/cp-library

:warning: 動的計画法/2次元累積和
(test/dynamic_programming/2d_cumulative_sum.test.cpp)

Depends on

Code

/*
 * @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;
}
Back to top page