Test/DataStructure/Accumulation_sum.test.cpp

View this file on GitHub
Last update: 2024-12-27 16:29:20+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0516

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0516"

#include <iostream>

#include <map>


// begin:tag includes

#include "./../../Library/DataStructure/Accumulation.hpp"

// end:tag includes


using ll = long long;

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

  do {
    ll n, k;
    std::cin >> n >> k;
    if (n == 0 && k == 0) { break; }

    std::vector<ll> a;
    a.reserve(n);
    for (int _ = 0; _ < n; ++_) {
      ll x;
      std::cin >> x;
      a.emplace_back(x);
    }

    auto acc = mtd::Accumulation<>(a);

    ll ans = -1e18;
    for (int i = 0; i < n - k + 1; ++i) {
      auto val = acc.get(i, i + k - 1);
      ans = std::max(ans, val);
    }
    std::cout << ans << std::endl;
  } while (true);
}

#line 1 "Test/DataStructure/Accumulation_sum.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0516"

#include <iostream>

#include <map>


// begin:tag includes

#line 2 "Library/DataStructure/Accumulation.hpp"

#include <algorithm>

#include <vector>


#line 2 "Library/Algebraic/Group.hpp"

#line 4 "Library/Algebraic/Group.hpp"

namespace mtd {

  template <class S,    // set
            S element,  // identity element
            class op,   // binary operation
            class inv   // inverse operation
            >
  requires std::is_invocable_r_v<S, op, S, S>
  struct Group {
    using value_type = S;
    constexpr static S _element = element;
    using op_type = op;
    using inv_type = inv;

    S m_val;
    constexpr Group() : m_val(element) {}
    constexpr Group(S val) : m_val(val) {}
    constexpr Group inverse() const { return inv()(m_val); }
    constexpr Group binaryOperation(const Group& g) const {
      return op()(m_val, g.m_val);
    }
    constexpr friend std::ostream& operator<<(
        std::ostream& os, const Group<S, element, op, inv>& g) {
      return os << g.m_val;
    }
  };

  namespace __detail {
    template <typename T,
              template <typename, auto, typename, typename> typename S>
    concept is_group_specialization_of = requires {
      typename std::enable_if_t<
          std::is_same_v<T, S<typename T::value_type, T::_element,
                              typename T::op_type, typename T::inv_type>>>;
    };
  }  // namespace __detail

  template <typename G>
  concept group = __detail::is_group_specialization_of<G, Group>;

}  // namespace mtd
#line 7 "Library/DataStructure/Accumulation.hpp"

namespace mtd {

  namespace type {

    using inv = decltype([](auto x) { return -x; });
    using op = decltype([](auto x, auto y) { return x + y; });
    template <class P>
    using AdditiveGroup = Group<P, P(0), op, inv>;

  }  // namespace type


  template <group Group = type::AdditiveGroup<long long>>
  class Accumulation {
    using S = decltype(Group().m_val);

    const int size;
    std::vector<Group> sumList;

  public:
    constexpr Accumulation() = delete;
    constexpr Accumulation(const std::vector<Group>& v)
        : size(v.size()), sumList(size + 1) {
      for (int i = 0; i < size; ++i) {
        sumList[i + 1] = sumList[i].binaryOperation(v[i]);
      }
    }
    constexpr Accumulation(const std::vector<S>& v)
        : Accumulation(std::vector<Group>(v.begin(), v.end())) {}

    constexpr auto get(int n) const { return sumList[n + 1].m_val; }
    constexpr auto get(int l, int r) const {
      if (r < l) { return Group::_element; }
      l = std::max(l, 0);
      r = std::min(r, size - 1);
      return sumList[r + 1].binaryOperation(sumList[l].inverse()).m_val;
    }

    constexpr friend std::ostream& operator<<(std::ostream& os,
                                              const Accumulation<Group>& acc) {
      for (const auto& x : acc.sumList) { os << x << " "; }
      return os;
    }
  };

}  // namespace mtd

#line 8 "Test/DataStructure/Accumulation_sum.test.cpp"
// end:tag includes


using ll = long long;

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

  do {
    ll n, k;
    std::cin >> n >> k;
    if (n == 0 && k == 0) { break; }

    std::vector<ll> a;
    a.reserve(n);
    for (int _ = 0; _ < n; ++_) {
      ll x;
      std::cin >> x;
      a.emplace_back(x);
    }

    auto acc = mtd::Accumulation<>(a);

    ll ans = -1e18;
    for (int i = 0; i < n - k + 1; ++i) {
      auto val = acc.get(i, i + k - 1);
      ans = std::max(ans, val);
    }
    std::cout << ans << std::endl;
  } while (true);
}