Submission #1865280

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <stack>
using namespace std;

inline int getint()
{
	static char c;
	while ((c = getchar()) < '0' || c > '9');

	int res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

template <class T>
inline void relax(T &a, const T &b)
{
	if (b > a)
		a = b;
}

typedef long long s64;

const int MaxN = 5000;
const int MaxM = 200;

int n, m;
int len[MaxN + 1];
int val[MaxN + 1][MaxM + 1];

s64 delta[MaxN + 1];

int sta[MaxM + 1][MaxN + 1];
int sta_n[MaxM + 1];

inline int query(int i, int k = 0)
{
	return sta[i][sta_n[i] - k];
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i < n; ++i)
		len[i] = getint();
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			val[i][j] = getint();

	s64 res = 0;
	for (int l = n; l >= 1; --l)
	{
		s64 sum = 0;
		for (int i = 1; i <= m; ++i)
		{
			while (sta_n[i] && val[query(i)][i] <= val[l][i])
			{
				if (sta_n[i] > 1)
				{
					int p = query(i);
					int q = query(i, 1);
					delta[q] -= val[q][i] - val[p][i];
				}

				--sta_n[i];
			}

			sta[i][++sta_n[i]] = l;

			if (sta_n[i] > 1)
			{
				int q = query(i, 1);
				delta[q] += val[q][i] - val[l][i];
			}

			sum += val[l][i];
		}

		s64 dist = 0;
		for (int r = l; r <= n; ++r)
		{
			sum += delta[r];
			relax(res, sum - dist);
			dist += len[r];
		}
	}

	cout << res << endl;

	return 0;
}

Submission Info

Judge Result