传送门

一直想$O(NM)$没什么思路,结果一看数据范围$N$是$5000$。。。

然后就是各种乱搞技巧了,我对每个颜色维护了一个单调栈,为了求每个颜色的后缀min的和,直接差分之后转成前缀和,然后每次暴力扫的过程中就能顺便求出来了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 5010
#define MAXM 210
#define LL long long
using namespace std;

int n,m;
LL d[MAXN];
LL a[MAXN][MAXM];
LL c[MAXN];

struct LCT{
    int f[MAXN];

    void init(){ for(int i=1;i<=n;i++) f[i]=i; }

    int access(int x){
        if(f[x]==x) return x;
        return f[x]=access(f[x]);
    }

    void link(int x,int y){
        access(x);
        access(y);
        if(f[x]^f[y]) f[f[y]]=f[x];
    }
}lct[MAXM];

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) lct[i].init();
    for(int i=2;i<=n;i++){
        scanf("%lld",d+i);
        d[i]+=d[i-1];
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%lld",&a[i][j]);
    LL ans=0;
    for(int i=1;i<=m;i++){
        ans+=a[1][i];
        c[1]+=a[1][i];
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=m;j++){
            int x=i-1;
            while(x && a[lct[j].access(x)][j]<a[i][j]){
                int y=lct[j].access(x);
                c[y]-=a[y][j]-a[lct[j].access(y-1)][j];
                lct[j].link(y,i);
                x=y-1;
            }
            a[x+1][j]=a[i][j];
            c[x+1]+=a[x+1][j]-a[lct[j].access(x)][j];
        }
        LL temp=0;
        for(int j=1;j<=i;j++){
            temp+=c[j];
            ans=max(ans,temp-d[i]+d[j]);
        }
    }
    printf("%lld\n",ans);
}