最小费用最大流。
请老实打！！！
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000000000
#define maxn 10010
using namespace std;
ll n,m,c[maxn];
ll cnt=1,hd[maxn];
ll ans,s,t;
ll pos[maxn],pre[maxn],pi[maxn];
ll dis[maxn];
ll vit[maxn];
struct Node{
ll nx,to,dis,val;
}e[maxn<<1];
struct NODE{
ll s,t,c;
}a[maxn<<1];
queue<ll>q;
inline ll read(){
ll x=0,f=0;char c=getchar();
while(!isdigit(c))
f|=c=='-',c=getchar();
while(isdigit(c))
x=(x<<1)+(x<<3)+(c^48),c=getchar();
return f?-x:x;
}
inline void add(ll u,ll v,ll w,ll val){
e[++cnt].to=v;
e[cnt].nx=hd[u];
e[cnt].dis=w;
e[cnt].val=val;
hd[u]=cnt;
}
inline int spfa(){
for(register int i=1;i<=t;++i)
vit[i]=0,dis[i]=INF;
vit[s]=1,dis[s]=0,
q.push(s),pi[s]=INF;
while(!q.empty()){
ll u=q.front();q.pop();
vit[u]=0;
for(register int i=hd[u];i;i=e[i].nx){
ll to=e[i].to;
if(e[i].dis&&dis[to]>dis[u]+e[i].val){
dis[to]=dis[u]+e[i].val;
pre[to]=u;
pos[to]=i;
pi[to]=min(pi[u],e[i].dis);
if(!vit[to]){
vit[to]=1;
q.push(to);
}
}
}
}
return (dis[t]!=INF);
}
// inline int spfa(){
// for(register int i=1;i<=t;++i)
// vit[i]=0,dis[i]=INF;
// q.push(s);
// vit[s]=1,dis[s]=0;
// pi[s]=INF;
// while(!q.empty()){
// ll u=q.front();q.pop();
// vit[u]=0;
// for(register int i=hd[u];i;i=e[i].nx){
// ll to=e[i].to,val=e[i].val;
// if(e[i].dis&&dis[to]>dis[u]+val){
// dis[to]=dis[u]+val;
// pos[to]=i;
// pre[to]=u;
// pi[to]=min(pi[u],e[i].dis);
// if(!vit[to]){
// vit[to]=1;
// q.push(to);
// }
// }
// }
// }
// return (dis[t]!=INF);
// }
int main(){
n=read();m=read();
s=2*n,t=s+1;
for(register int i=1;i<=n;++i)
c[i]=read();
for(register int i=1;i<=m;++i){
a[i].s=read();a[i].t=read();a[i].c=read();
add(a[i].s,a[i].t+1,INF,a[i].c),
add(a[i].t+1,a[i].s,0,-a[i].c);
}
for(register int i=1;i<=n;++i)
add(i,i+1,INF-c[i],0),
add(i+1,i,0,0);
add(s,1,INF,0),add(1,s,0,0),add(n+1,t,INF,0),add(t,n+1,0,0);
ans=0;
while(spfa()){
ans+=dis[t]*pi[t];
for(register int i=t;i!=s;i=pre[i]){
e[pos[i]].dis-=pi[t];
e[pos[i]^1].dis+=pi[t];
}
}
printf("%lld\n",ans);
return 0;
}
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000000000
#define maxn 100000
using namespace std;
ll N,a[maxn];
ll p,m,f,n,ss;
ll s,t;
ll ans;
ll pi[maxn],pos[maxn],pre[maxn];
ll dis[maxn];
struct Node{
ll nx,to,val,dis;
}e[maxn<<2];
ll cnt=1,hd[maxn];
ll vit[maxn];
queue<ll>q;
inline ll read(){
ll x=0,f=0;char c=getchar();
while(!isdigit(c))
f|=c=='-',c=getchar();
while(isdigit(c))
x=(x<<1)+(x<<3)+(c^48),c=getchar();
return f?-x:x;
}
inline void add(ll u,ll v,ll dis,ll vl){
e[++cnt].to=v;
e[cnt].nx=hd[u];
e[cnt].dis=dis;
e[cnt].val=vl;
hd[u]=cnt;
}
inline ll sm(ll k){
return k+N;
}
inline int spfa(){
for(register int i=1;i<=t;++i)
vit[i]=0,dis[i]=INF;
q.push(s);
vit[s]=1,dis[s]=0;
pi[s]=INF;
while(!q.empty()){
ll u=q.front();q.pop();
vit[u]=0;
for(register int i=hd[u];i;i=e[i].nx){
ll to=e[i].to,val=e[i].val;
if(e[i].dis&&dis[to]>dis[u]+val){
dis[to]=dis[u]+val;
pre[to]=i;
pos[to]=u;
pi[to]=min(pi[u],e[i].dis);
if(!vit[to]){
vit[to]=1;
q.push(to);
}
}
}
}
return (dis[t]!=INF);
}
int main(){
N=read();
for(register int i=1;i<=N;++i)
a[i]=read();
p=read();m=read();f=read();n=read();ss=read();
t=N*3+2;
s=t-1;
for(register int i=1;i<=N;++i){
add(s,i,a[i],0),
add(i,s,0,0),
add(sm(i),t,a[i],0),
add(t,sm(i),0,0);
if(i+1<=N)
add(i,i+1,INF,0),
add(i+1,i,0,0);
if(i+m<=N)
add(i,sm(i+m),INF,f),
add(sm(i+m),i,0,-f);
if(i+n<=N)
add(i,sm(i+n),INF,ss),
add(sm(i+n),i,0,-ss);
add(s,sm(i),INF,p),
add(sm(i),s,0,-p);
}
ans=0;
while(spfa()){
ans+=pi[t]*dis[t];
for(register int i=t;i!=s;i=pos[i]){
e[pre[i]].dis-=pi[t];
e[pre[i]^1].dis+=pi[t];
}
}
printf("%lld\n",ans);
return 0;
}
