Portals

D - Portals

参考：CF1271D Portals dp 贪心

代码：

// Created by CAD on 2020/1/7.
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn=5005;
int last[maxn],a[maxn],b[maxn],c[maxn];
priority_queue<int> value[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i)
        cin>>a[i]>>b[i]>>c[i],last[i]=i;
    for(int i=1,u,v;i<=m;++i)
        cin>>u>>v,last[v]=max(last[v],u);
    for(int i=1;i<=n;++i)
        value[last[i]].push(c[i]);
    priority_queue<int,vector<int>,greater<int> > q;
    ll sum=k;
    for(int i=1;i<=n+1;++i)         //边界为n+1的原因是要保证sum的值非负，且要得到最优值
    {
        while((!q.empty())&&sum<a[i])
            sum++,q.pop();
        if(sum<a[i])
            return puts("-1");
        sum+=b[i];
        while(!value[i].empty())
            sum--,q.push(value[i].top()),value[i].pop();
    }
    ll ans=0;
    while(!q.empty())
        ans+=q.top(),q.pop();
    cout<<ans<<endl;
    return 0;
}

几个毒瘤数据：