Language: C++


#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <queue>

template <class T, class U>
inline bool chmin(T &lhs, const U &rhs) {
  if (lhs > rhs) { lhs = rhs; return true; }
  return false;
}

template <class T, class U>
inline bool chmax(T &lhs, const U &rhs) {
  if (lhs < rhs) { lhs = rhs; return true; }
  return false;
}

struct range {
  using itr = int64_t;
  struct iterator {
    itr i;
    constexpr iterator(itr i_): i(i_) { }
    constexpr void operator ++ () { ++i; }
    constexpr itr operator * () const { return i; }
    constexpr bool operator != (iterator x) const { return i != x.i; }
  };
  const iterator l, r;
  constexpr range(itr l_, itr r_): l(l_), r(std::max(l_, r_)) { }
  constexpr iterator begin() const { return l; }
  constexpr iterator end() const { return r; }
};

struct revrange {
  using itr = int64_t;
  struct iterator {
    itr i;
    constexpr iterator(itr i_): i(i_) { }
    constexpr void operator ++ () { --i; }
    constexpr itr operator * () const { return i; }
    constexpr bool operator != (iterator x) const { return i != x.i; }
  };
  const iterator l, r;
  constexpr revrange(itr l_, itr r_): l(l_ - 1), r(std::max(l_, r_) - 1) { }
  constexpr iterator begin() const { return r; }
  constexpr iterator end() const { return l; }
};


template <class T>
class disjoint_sparse_table {
public:
  using value_type = typename T::value_type;
  static inline const auto op = typename T::value_operation();

private:
  std::vector<std::vector<value_type>> table;

public: 
  disjoint_sparse_table() = default;
  disjoint_sparse_table(const std::vector<value_type> &table_) { build(table_); }

  void build(const std::vector<value_type> &table_) {
    int height = 0, size = table_.size();
    while ((1 << height) < size) ++height;
    if (size == 1) ++height;
    table.assign(height, std::vector<value_type>(size));
    for (int i = 0; i < size; ++i) {
      table[0][i] = table_[i];
    }
    for (int i = 1; i < height; ++i) {
      int bit = (1 << i);
      for (int l = 0; l < size; l += (bit << 1)) {
        int m = (l + bit < size ? l + bit : size);
        table[i][m - 1] = table_[m - 1];
        for (int j = m - 2; j >= l; --j) {
          table[i][j] = op(table_[j], table[i][j + 1]);
        }
        if (m >= size) continue;
        int r = (m + bit < size ? m + bit : size);
        table[i][m] = table_[m];
        for (int j = m + 1; j < r; ++j) {
          table[i][j] = op(table[i][j - 1], table_[j]);
        }
      }
    }
  }

  value_type fold(int l, int r) const {
    if (l >= --r) return table[0][l];
    int h = 31 - __builtin_clz(l ^ r);
    return op(table[h][l], table[h][r]);
  }

};

using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;

constexpr i32 inf32 = (i32(1) << 30) - 1;
constexpr i64 inf64 = (i64(1) << 62) - 1;

struct range_max {
  using value_type = i32;
  struct value_operation {
    value_type operator () (const value_type &x, const value_type &y) const {
      return std::max(x, y);
    }
  };
};

#ifdef LOCAL
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <ctime>

struct debug_support {

  std::ofstream file;
  std::stringstream to_str_helper;
  const std::clock_t start_time;

  debug_support(): start_time(std::clock()) {
    file.open("debug.txt");
    if (!file.is_open()) {
      std::cerr << "\033[31m failed to open the file 'debug.txt' \033[0m \n";
      std::exit(EXIT_FAILURE);
    }
    file << "\n<debug output file>\n\n";
    to_str_helper << std::boolalpha;
    to_str_helper << std::fixed;
  }
  ~debug_support() {
    file.close(); 
  }

  std::string to_str(char c) { 
    return std::string("'") + c + "'"; 
  }
  std::string to_str(const std::string &s) { 
    return std::string("\"") + s + "\""; 
  }
  std::string to_str(const char *s) { 
    return std::string("\"") + s + "\""; 
  }

  template <class T, class U>
  std::string to_str(const std::pair<T, U> &x) { 
    return "(" + to_str(x.first) + ", " + to_str(x.second) + ")"; 
  }
  template <class T, size_t I>
  typename std::enable_if<(I + 1 == std::tuple_size<T>::value), std::string>::type to_str_tuple(const T &x) { 
    return to_str(std::get<I>(x)); 
  } 
  template <class T, size_t I>
  typename std::enable_if<(I + 1 != std::tuple_size<T>::value), std::string>::type to_str_tuple(const T &x) { 
    return to_str(std::get<I>(x)) + ", " + to_str_tuple<T, I + 1>(x);
  } 
  template <class... Args>
  std::string to_str(const std::tuple<Args...> &x) {
    return "(" + to_str_tuple<std::tuple<Args...>, 0>(x) + ")";
  }

  template <class T>
  std::string to_str(const T &x) {
    to_str_helper << x;
    std::string s;
    std::getline(to_str_helper, s);
    to_str_helper.str("");
    to_str_helper.clear(std::stringstream::goodbit);
    return s;
  }
  template <class T, class U, class... Args>
  std::string to_str(const T &x, const U &y, const Args&... args) { 
    return x == y ? "__" : to_str(x, args...); 
  }

  template <class T>
  void print(const T &x) { 
    file << to_str(x) << std::endl;
  }
  template <class T, class... Args>
  void print(const T &x, const Args&... args) {
    file << to_str(x) << ", ";
    print(args...);
  }

  template<typename T, typename _ = void>
  struct has_iterator: public std::false_type {};
  template<typename T>
  struct has_iterator<T, typename std::conditional<false, typename T::iterator, void>::type>: public std::true_type {};

  template <class T, class... Args>
  typename std::enable_if<has_iterator<typename T::value_type>::value == true, std::string>::type 
  to_str_container(const T &x, const Args&... args) {
    std::string s;
    for (const auto &v: x) {
      s += to_str_container(v, args...);
    }
    return s + '\n';
  }
  template <class T, class... Args>
  typename std::enable_if<has_iterator<typename T::value_type>::value == false, std::string>::type 
  to_str_container(const T &x, const Args&... args) {
    std::string s = "{ ";
    bool f = false;
    for (const auto &v: x) {
      if (f) s += ", ";
      f = true;
      s += to_str(v, args...);
    }
    return s + " }\n";
  }

  template <class T, class... Args>
  void print_container(const T &x, const Args&... args) {
    file << to_str_container(x, args...) << std::flush;
  }

  void show_c_impl(const std::string &s) {
    auto i = s.begin();
    while (i != s.end() && *i != ',') ++i;
    file << " [" << std::string(s.begin(), i) << "]";
    if (i != s.end()) file << " (ignore" << std::string(i + 1, s.end()) << ")";
    file << ":\n";
  }

} debugger;

#define show(...)\
  do {\
    debugger.file << "<line:" << std::setw(4) << __LINE__ << "> [";\
    debugger.file << #__VA_ARGS__ << "]: ";\
    debugger.print(__VA_ARGS__);\
  } while (false)

#define show_c(...)\
  do {\
    debugger.file << "\n<line:" << std::setw(4) << __LINE__ << ">";\
    debugger.show_c_impl(#__VA_ARGS__);\
    debugger.print_container(__VA_ARGS__);\
    debugger.file << std::endl;\
  } while (false)

#define showtime()\
  do {\
    double d = static_cast<double>(std::clock() - debugger.start_time);\
    debugger.file << "<line:" << std::setw(4) << __LINE__ << ">";\
    debugger.file << " elapsed time: " << d * 1000 / CLOCKS_PER_SEC << "ms" << std::endl;\
  } while (false)

#else
#define show(...) ((void) 0)
#define show_c(...) ((void) 0)
#define showtime() ((void) 0)
#endif

int main() {
  size_t N, M;
  std::cin >> N >> M;
  std::vector<i32> A(N);
  for (auto i: range(1, N)) {
    std::cin >> A[i];
    A[i] += A[i - 1];
  }
  std::vector<std::vector<i32>> B_impl(M, std::vector<i32>(N));
  for (auto i: range(0, N)) {
    for (auto j: range(0, M)) {
      std::cin >> B_impl[j][i];
    }
  }
  std::vector<disjoint_sparse_table<range_max>> B(M);
  for (auto i: range(0, M)) {
    B[i].build(B_impl[i]);
  }
  struct query { i32 l, r, d, u; };
  std::queue<query> que;
  que.push(query{ 0, N, 0, N - 1 });
  i64 ans = -inf64;
  while (!que.empty()) {
    auto q = que.front();
    que.pop();
    i32 ml = (q.l + q.r) / 2;
    i64 max = -inf64;
    i32 mr = ml;
    for (auto i: range(std::max(ml, q.d), q.u + 1)) {
      i64 sum = A[ml] - A[i];
      for (auto j: range(0, M)) {
        sum += B[j].fold(ml, i + 1);
      }
      show(ml, i, A[i], A[ml], sum);
      if (chmax(max, sum)) {
        mr = i;
      }
    }
    chmax(ans, max);
    if (q.r - q.l > 1) {
      que.push(query{ q.l, ml, q.d, mr });
      que.push(query{ ml, q.r, mr, q.u });
    }
  }
  std::cout << ans << '\n';
  return 0;
}


Compiler output:
a.cc:102:13: error: 'uint32_t' does not name a type
  102 | using u32 = uint32_t;
      |             ^~~~~~~~
a.cc:9:1: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
    8 | #include <queue>
  +++ |+#include <cstdint>
    9 | 
a.cc:103:13: error: 'uint64_t' does not name a type
  103 | using u64 = uint64_t;
      |             ^~~~~~~~
a.cc:103:13: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
a.cc: In function 'int main()':
a.cc:285:22: warning: narrowing conversion of 'N' from 'size_t' {aka 'long unsigned int'} to 'i32' {aka 'int'} [-Wnarrowing]
  285 |   que.push(query{ 0, N, 0, N - 1 });
      |                      ^
a.cc:285:30: warning: narrowing conversion of '(N - 1)' from 'size_t' {aka 'long unsigned int'} to 'i32' {aka 'int'} [-Wnarrowing]
  285 |   que.push(query{ 0, N, 0, N - 1 });
      |                            ~~^~~