题解

#include<bits/stdc++.h>
#define FOR(i,x,y) for(register int i=(x);i<=(y);++i)
#define DOR(i,x,y) for(register int i=(x);i>=(y);--i)
#define N 1003
#define M 10003
typedef long long LL;
using namespace std;
int onbus[N],cnt[N],D[N],S[N],T[M],A[M],B[M];
int n,m,K;
struct node
{
    int l,r;  
    bool operator <(const node &_)const{return cnt[r]-cnt[l-1]<cnt[_.r]-cnt[_.l-1];}
};
priority_queue<node>q;

int main()
{
    cin>>n>>m>>K;
    FOR(i,1,n-1) cin>>D[i];
    FOR(i,1,m)
    {
        cin>>T[i]>>A[i]>>B[i];
        onbus[A[i]]=max(onbus[A[i]],T[i]);
        cnt[B[i]]++;
    }
    FOR(i,2,n)cnt[i]+=cnt[i-1];
    FOR(i,2,n)S[i]=max(S[i-1],onbus[i-1])+D[i-1];
    FOR(i,2,n)
        if(S[i]>onbus[i])
        {
            FOR(j,i,n)
                if(j==n||S[j]<=onbus[j])
                {
                    q.push((node){i,j});
                    i=j;
                    break;
                }
        }
    while(!q.empty()&&K>0)
    {
        node now=q.top();q.pop();
        int miner=min(K,D[now.l-1]),p=-1;
        FOR(i,now.l,now.r-1)
            if(S[i]-onbus[i]<miner)
            {
                miner=S[i]-onbus[i];
                p=i;
            }
        D[now.l-1]-=miner,K-=miner;
        FOR(i,now.l,now.r)S[i]=max(S[i-1],onbus[i-1])+D[i-1];
        if(~p)q.push((node){now.l,p}),q.push((node){p+1,now.r});
        else if(now.l<now.r)q.push((node){now.l+1,now.r}); 
    }
    int ans=0;
    FOR(i,1,m)ans+=S[B[i]]-T[i];
    cout<<ans<<'\n';
    return 0;
}

时间最优