Language: C++


#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

using P = pair<LL, LL>;


template <class T>
struct my_greater : std::greater<T>
{
	static constexpr T defval = std::numeric_limits<T>::min();
};


template <>
struct my_greater<P> : std::greater<P>
{
	static constexpr P defval = P(std::numeric_limits<LL>::min(), std::numeric_limits<LL>::min());
};

//Base class for Segment Trees
template <class T>
class segtree_base
{
protected:
	size_t width;
	vector<T> vec;
	T def;
	virtual T query_raw(int l_, int r_, int a_, int b_, int k_) = 0;
public:
	segtree_base(size_t size_, const T& def_ = T()) : def(def_)
	{
		width = 1;
		while (width < size_)width *= 2;
		vec.resize(width * 2 - 1, def);
	}
	//Ask a query in ranges [left,right)
	T query(int left, int right)
	{
		return query_raw(left, right, 0, width, 0);
	}
	//Get the number of child nodes
	size_t treeWidth()
	{
		return width;
	}
	virtual ~segtree_base() {}
};

//Range Minimum Tree
template <class T, class Comp>
class rmq_tree : public segtree_base<T>
{
public:
	rmq_tree(size_t size_) : segtree_base<T>(size_, Comp()::defval)
	{}

	//Do [] <= base
	void init(const vector<T>&base)
	{
		for (int i = 0; i < min(this->width, base.size()); i++) this->vec[i + this->width - 1] = base[i];
		for (int i = this->width - 2; i >= 0; i--) this->vec[i] = std::min(this->vec[i * 2 + 1], this->vec[i * 2 + 2], Comp());
	}

	//Make [index] <= val;
	void update(int index, T val)
	{
		auto &vec = this->vec;
		index += (this->width - 1);
		vec[index] = val;
		while (index > 0)
		{
			index = (index - 1) / 2;
			vec[index] = std::min(vec[index * 2 + 1], vec[index * 2 + 2], Comp());
		}
	}
private:
	T query_raw(int l_, int r_, int a_, int b_, int k_)override
	{
		const auto &vec = this->vec;
		if (l_ <= a_ && b_ <= r_)
		{
			return vec[k_];
		}
		if (b_ <= l_ || r_ <= a_)
		{
			return this->def;
		}
		int m = (a_ + b_) / 2;
		return std::min(
			query_raw(l_, r_, a_, m, k_ + k_ + 1),
			query_raw(l_, r_, m, b_, k_ + k_ + 2), Comp());
	}
};




template<typename T>
class imos2d
{
private:
	std::vector<std::vector<T>>buf;
	const int lim1, lim2;
	bool convert;
	inline bool valid(int x, int y, bool wide)
	{
		return (0 <= x && 0 <= y && x < lim1 + (wide ? 1 : 0) && y < lim2 + (wide ? 1 : 0));
	}
	T rawsum(int i1, int i2)
	{
		assert(valid(i1, i2, true));
		return buf[i1][i2];
	}
public:
	//サイズを指定してください
	imos2d(size_t width, size_t height) :
		lim1(width), lim2(height),
		convert(false)
	{
		buf.resize(width + 1, std::vector<T>(height + 1));
	}
	//１マスをマーキングする(splatと併用不可)
	void mark(int first, int second, T value)
	{
		assert(!convert);
		assert(valid(first, second, false));
		buf[first + 1][second + 1] += value;
	}
	//区域内でマーキングした和を求める(markのみに使用)
	T sumquery(int firstcor, int secondcor, int firstlen, int secondlen)
	{
		assert(convert);
		int px = firstcor, py = secondcor;
		int qx = px + firstlen, qy = py + secondlen;
		assert(valid(px, py, false) && valid(qx, qy, true));
		return rawsum(px, py) + rawsum(qx, qy) - rawsum(px, qy) - rawsum(qx, py);
	}
	//範囲を塗りつぶす(markと併用不可)
	void splat(int firstcor, int secondcor, int firstlen, int secondlen, T value)
	{
		assert(!convert);
		int px = firstcor, py = secondcor;
		int qx = px + firstlen, qy = py + secondlen;
		assert(valid(px, py, false) && valid(qx, qy, true));
		buf[px][py] += value;
		buf[qx][qy] += value;
		buf[px][qy] -= value;
		buf[qx][py] -= value;
	}
	//あるマスの重なりを調べる(splatのみに使用)
	T depth(int first, int second)
	{
		assert(convert);
		assert(valid(first, second, false));
		return buf[first][second];
	}
	//累積する
	void imos()
	{
		convert = true;
		for (int i = 0; i < lim1; ++i)
		{
			for (int j = 0; j <= lim2; ++j)
			{
				buf[i + 1][j] += buf[i][j];
			}
		}
		for (int i = 0; i <= lim1; ++i)
		{
			for (int j = 0; j < lim2; ++j)
			{
				buf[i][j + 1] += buf[i][j];
			}
		}
	}
};

vector<rmq_tree<P, my_greater<P>>>vec;

LL B[5678][234];

//k種類目のチケットを値域[i,j)においてみる
void bury(imos2d<LL>&imos, int k, int i, int j)
{
	if (i == j)return;
	auto ret = vec[k].query(i, j);
	LL val = ret.first;
	int index = ret.second;
	int lef = i;
	int upp = index;
	int wid = index - i + 1;
	int hei = j - index;
	imos.splat(lef, upp, wid, hei, val);
	bury(imos, k, i, index);
	bury(imos, k, index + 1, j);
}


int main(void)
{
	LL N, M;
	vector<LL>dist(1, 0);
	cin >> N >> M;
	for (int i = 1; i < N; ++i)
	{
		LL a;
		cin >> a;
		dist.push_back(dist.back() + a);
	}
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			cin >> B[i][j];
		}
	}
	for (int j = 0; j < M; ++j)
	{
		vec.push_back(rmq_tree<P, my_greater<P>>(N));
		auto& seg = vec.back();
		vector<P>cash;
		for (int i = 0; i < N; ++i)cash.push_back({ B[i][j],i });
		seg.init(cash);
	}

	imos2d<LL>base(N, N);

	for (int k = 0; k < M; ++k)
	{
		bury(base, k, 0, N);
	}

	base.imos();

	LL ans = 0;
	for (int r = 0; r < N; ++r)
	{
		for (int l = 0; l <= r; ++l)
		{
			LL minus = dist[r] - dist[l];
			LL cue = base.depth(l, r);
			cue -= minus;
			ans = max(ans, cue);
		}
	}

	cout << ans << endl;
	return 0;
}


Compiler output:
a.cc: In constructor 'rmq_tree<T, Comp>::rmq_tree(size_t)':
a.cc:80:63: error: expected ')' before '::' token
   80 |         rmq_tree(size_t size_) : segtree_base<T>(size_, Comp()::defval)
      |                                                               ^~
a.cc:80:49: note: to match this '('
   80 |         rmq_tree(size_t size_) : segtree_base<T>(size_, Comp()::defval)
      |                                                 ^
a.cc: In instantiation of 'rmq_tree<T, Comp>::rmq_tree(size_t) [with T = std::pair<long long int, long long int>; Comp = my_greater<std::pair<long long int, long long int> >; size_t = long unsigned int]':
a.cc:245:45:   required from here
  245 |                 vec.push_back(rmq_tree<P, my_greater<P>>(N));
      |                                                           ^
a.cc:80:71: error: no matching function for call to 'segtree_base<std::pair<long long int, long long int> >::segtree_base(size_t&, my_greater<std::pair<long long int, long long int> >)'
   80 |         rmq_tree(size_t size_) : segtree_base<T>(size_, Comp()::defval)
      |                                                                       ^
a.cc:56:9: note: candidate: 'segtree_base<T>::segtree_base(size_t, const T&) [with T = std::pair<long long int, long long int>; size_t = long unsigned int]'
   56 |         segtree_base(size_t size_, const T& def_ = T()) : def(def_)
      |         ^~~~~~~~~~~~
a.cc:56:45: note:   no known conversion for argument 2 from 'my_greater<std::pair<long long int, long long int> >' to 'const std::pair<long long int, long long int>&'
   56 |         segtree_base(size_t size_, const T& def_ = T()) : def(def_)
      |                                    ~~~~~~~~~^~~~~~~~~~
a.cc:48:7: note: candidate: 'segtree_base<std::pair<long long int, long long int> >::segtree_base(const segtree_base<std::pair<long long int, long long int> >&)'
   48 | class segtree_base
      |       ^~~~~~~~~~~~
a.cc:48:7: note:   candidate expects 1 argument, 2 provided