讲道理,这题是真的lj.盗题就算了,题面还这么糟糕...
贪心+dp不解释.https://ac.nowcoder.com/acm/problem/21314 具体看这题.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=55,M=1e6+60;
struct Dp{
    ll a,b,c;
}food[N];
ll f[M];ll val[N];
bool cmp(Dp A,Dp B)
{
    return B.c*A.b>A.c*B.b;
}

int main()
{
    int n,m,T;
    scanf("%d%d%d",&n,&m,&T);
    for(int i=1;i<=n;i++)    scanf("%lld",&val[i]);
    for(int i=1;i<=m;i++)
    {
        int id;scanf("%d",&id);
        food[i].b=val[id];
        scanf("%lld%lld",&food[i].a,&food[i].c);
    }sort(food+1,food+1+m,cmp);
    memset(f,-0x3f,sizeof f);
    ll ans=-1e18;f[0]=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=T;j-food[i].c>=0;j--)
        {    
            ll time=j;
            f[j]=max(f[j],f[j-food[i].c]+food[i].a-time*food[i].b);
            ans=max(ans,f[j]);
        }
    }printf("%lld\n",ans);
    return 0;
}