[ARC067F] Yakiniku Restaurants

首先考虑暴力。\(\mathcal O(n^2m)\) 枚举左右两个端点，再贪心地选其中 \(M\) 张票的美味度最大那一家餐馆。复杂度不可接受，但是不难感觉到正解应该是 \(\mathcal O(n^2)\) 的。

考虑枚举左端点 \(i\)，对于当前左端点，记每一个右端点 \(j\) 的答案为 \(now_j\)，若暂时不考虑距离，大部分 \(now_j\) 会从 \(i + 1\) 继承过来，而少量的 \(now_j\) 则会因为 \([i+1,j]\) 中选择的最大值比 \(i\) 这个餐馆小而变大。

发现这是一个类似单调栈的过程，\(M\) 张票互相独立。对于每一张票，若其选择的餐馆编号在 \(i\) 之后，且美味度小于 \(i\)则其没有意义（选择编号更小的且美味度更大的显然更好）。那么弹出栈顶元素 sk[top]，发现编号为 sk[top] 至 sk[top-1]-1 的点都原本选择 sk[top] 作为餐馆，而现在全都选择 \(i\) 号餐馆。于是差分维护变化量即可。

const int N = 5e3 + 5, M = 205;
ll b[M][N], a[N], d[N];
void add(int l, int r, int k) {d[l] += k, d[r + 1] -= k;}
int sk[M][N]; int top[M];
ll n, m, ans, now[N];
signed main() 
{
    cin >> n >> m;
    R(i, 1, n - 1) cin >> a[i];
    R(i, 1, n)
        R(j, 1, m) cin >> b[j][i];
    R(i, 1, m) sk[i][0] = n + 1;
    for (int i = n; i; --i)
    {
        R(j, 1, m)
        {
            now[i] += b[j][i];
            while (top[j] && b[j][sk[j][top[j]]] <= b[j][i]) add(sk[j][top[j]], sk[j][top[j] - 1] - 1, b[j][i] - b[j][sk[j][top[j]]]), --top[j];
            sk[j][++top[j]] = i;
        }
        add(i + 1, n, -a[i]);
        ll tmp = 0;
        R(j, i, n)
        {
            tmp += d[j]; d[j] = 0;
            now[j] += tmp; ans = max(ans, now[j]);
            // cout << i << ' ' << j << ' ' << d[j] << ' '<< tmp << ' ' << now[j] << '\n';
        }
    }
    cout << ans << endl;
    return 0;
}