NOIP观光公交

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

int read()

{

    int x=,f=;char ch=getchar();

    while(ch<'' || ch>'')

    {

        if(ch=='-') f=-;

        ch=getchar();

    }

    while(ch>='' && ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

int n,m,k,d[],maxt[],sum[],g[],t[],car[],a[],b[];

int ans,maxn,fast;

int i;

int main()

{

    n=read(); m=read(); k=read();

    for(i=;i<n;i++) d[i]=read();

    for(i=;i<=m;i++)

    {

        t[i]=read(); a[i]=read(); b[i]=read();

        maxt[a[i]]=max(maxt[a[i]],t[i]);

        sum[b[i]]++;

    }

    for(i=;i<=n;i++) sum[i]+=sum[i-];

    car[]=maxt[];

    for(i=;i<=n;i++)

    {

        car[i]=max(car[i-],maxt[i-]);

        car[i]+=d[i-];

    }

    for(i=;i<=m;i++)

    {

        ans+=car[b[i]]-t[i];

    }

    while(k--)

    {

        g[n]=g[n-]=n;

        maxn=;

        for(i=n-;i>=;i--)

        {

            if(car[i+]<=maxt[i+])

                g[i]=i+;

            else g[i]=g[i+];

        }

        for(i=;i<n;i++)

        {

            if(sum[g[i]]-sum[i]>maxn && d[i]!=)

            {

                maxn=sum[g[i]]-sum[i];

                fast=i;

            }

        }

        ans-=maxn;

        d[fast]--;

        for(i=;i<=n;i++)

        {

            car[i]=max(car[i-],maxt[i-]);

            car[i]+=d[i-];

        }

    }

    printf("%d",ans);

    return ;

}

观光公交