UOJ

分析

这个东西相当于洞有容量上限和额外代价，因此可以考虑模拟费用流。

我们维护两个堆，分别代表洞和老鼠，然后从左往右扫

• 如果当前是老鼠，取出一个代价最小的洞，代价即为 $x+cost$；后面有可能反悔，即让右边的一个洞匹配这只老鼠，所以要向老鼠堆中加入 $-(x+cost)-x$。
• 如果当前是洞，取出一只代价最小的老鼠，代价即为 $y+cost+w$；后面有可能反悔，即让右边的一只老鼠匹配这个洞，所以要向洞堆中加入 $-(y+cost+w)-y+w$；还有可能让右边的一个洞匹配当前的洞匹配的老鼠，因此还要向老鼠堆中加入 $-y-w$。如果当前的洞匹配完后还有剩余容量也要加入洞堆中。

然而这样子可能向洞堆中加入 $\sum c_i$ 个元素，所以我们在堆中存一个 pair，记下代价和出现次数即可。又因为一个匹配中的老鼠和堆不会同时反悔，所以只会操作 $\mathcal{O}(n)$ 次，故时间复杂度 $\mathcal{O}(n\log n)$。

代码

看到了一个神奇的 mutable 的写法，于是学习了一下。

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int inf=0x3f3f3f3f;

int n,m,x[N],y[N],w[N],c[N];
struct node { ll cost; mutable int cnt; };
bool operator <(node a,node b) { return a.cost>b.cost; }
priority_queue<node> M,H;
ll ans=0;

void addmouse(int x) {
    ll cost=inf;
    if (!H.empty()) {
        cost=H.top().cost+x;
        if (!(--H.top().cnt)) H.pop();
    }
    ans+=cost,M.push((node){-cost-x,1});
}
void addhole(int y,int w,int c) {
    int s=0;
    while (!M.empty()&&s<c) {
        ll cost=M.top().cost+y+w;
        if (cost>=0) break;
        int f=min(M.top().cnt,c-s);
        ans+=cost*f,s+=f,H.push((node){-cost-y+w,f});
        if (!(M.top().cnt-=f)) M.pop();
    }
    if (s) M.push((node){-y-w,s});
    if (c-s) H.push((node){-y+w,c-s});
}

int main() {
    n=read(),m=read(); ll s=0;
    for (int i=1;i<=n;++i) x[i]=read();
    for (int i=1;i<=m;++i) y[i]=read(),w[i]=read(),c[i]=read(),s+=c[i];
    if (s<n) { puts("-1"); return 0; }
    for (int i=1,j=1;i<=n||j<=m;) {
        if (i<=n&&(j>m||x[i]<y[j])) addmouse(x[i]),++i;
        else addhole(y[j],w[j],c[j]),++j;
    }
    printf("%lld\n",ans);
    return 0;
}