题意
首先因为每个值只会被算一次且值的个数为(n^2)级别的，因此我们可以对每个(d_{i,j})开一个点，之后就可以用最大权闭合子图做。
考虑题目的限制：
1.选择一个区间([l,r])会将(sumlimits_{i=l}^{r}sumlimits_{j=i+1}^rd_{i,j})选上:
我们显然不能全部连上，这是(n^4)级别的，我们可以只从(d_{i,j})向(d_{i+1,j})和(d_{i,j-1})连边。
2.如果吃过(c)种代号为(x)的寿司，会付出(m*x^2+c*x)的代价:
拆成两部分：
<1>选了(c)种代号为(x)的寿司会付出(c*x)的代价，即选了(d_{i,i})就必定要付出(a_i)的代价。
<2>如果选了代号为(x)的寿司，就会付出(m*x^2)的代价：
我们对每个(a_i)也开一个点，点权为(-a_i^2)。
于是总结下连边是这样的：
对于(d_{i,j})：
如果(i=j)：
从(d_{i,i})向(a_i)连一条容量为(inf)的边，表示选了第(i)个就选了第(a_i)种。从(d_{i,j})向汇点连一条容量为(a_i)的边，表示选了(i)号寿司需要付出(a_i)的代价。
反之：
从(d_{i,j})向(d_{i+1,j})和(d_{i,j-1})连容量为(inf)的边。
最后根据点权正负向源点和汇点连边。
code:
#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
const int inf=1e9;
int n,m,num,cnt=1,S,T,tot,ans;
int a[maxn],head[maxn*maxn+maxn],cur[maxn*maxn+maxn],dep[maxn*maxn+maxn];
int val[maxn][maxn],id[maxn][maxn];
struct edge{int to,nxt,flow;}e[(maxn*maxn+maxn)<<2];
inline void add(int u,int v,int w)
{
e[++cnt].nxt=head[u];
head[u]=cnt;
e[cnt].to=v;
e[cnt].flow=w;
}
inline bool bfs()
{
memset(dep,0,sizeof(dep));
for(int i=S;i<=T;i++)cur[i]=head[i];
queue<int>q;
q.push(S);dep[S]=1;
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(dep[y]||e[i].flow<=0)continue;
dep[y]=dep[x]+1;q.push(y);
}
}
return dep[T]>0;
}
int dfs(int x,int goal,int lim)
{
if(x==goal||lim<=0)return lim;
int res=lim;
for(int i=cur[x];i;i=e[i].nxt)
{
cur[x]=i;
int y=e[i].to;
if(dep[y]!=dep[x]+1||e[i].flow<=0)continue;
int tmp=dfs(y,goal,min(res,e[i].flow));
if(tmp<=0)dep[y]=0;
res-=tmp;
e[i].flow-=tmp,e[i^1].flow+=tmp;
if(res<=0)break;
}
return lim-res;
}
inline int Dinic()
{
int res=0;
while(bfs())res+=dfs(S,T,inf);
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),num=max(num,a[i]);
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
scanf("%d",&val[i][j]),id[i][j]=++tot;
S=0,T=tot+num+1;
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
{
int w=val[i][j];
if(i==j)
{
if(m)add(id[i][j],tot+a[i],inf),add(tot+a[i],id[i][j],0);
w-=a[i];
}
else
{
add(id[i][j],id[i+1][j],inf),add(id[i+1][j],id[i][j],0);
add(id[i][j],id[i][j-1],inf),add(id[i][j-1],id[i][j],0);
}
if(w>=0)ans+=w,add(S,id[i][j],w),add(id[i][j],S,0);
else add(id[i][j],T,-w),add(T,id[i][j],0);
}
if(m)
for(int i=1;i<=num;i++)
add(tot+i,T,i*i),add(T,tot,0);
printf("%d",ans-Dinic());
return 0;
}