4月28日 美味菜肴 贪心+01背包

 #include<bits/stdc++.h>
#define LL long long
using namespace std;

struct Node{
    LL a, b, c;
}a[1000005];
LL b[1000005], f[1000005];

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

    return 0;
}