【每日一题】美味佳肴 4.27

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e6+7;
const int inf = 0x3f3f3f3f;
ll dp[maxn],f[55];

struct node{
    ll a,b,c;

    bool operator < (const node& x)const
    {
        return c*x.b<x.c*b;
    }
}p[55];


int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m,T;
    cin>>n>>m>>T;
    for(int i=1;i<=n;i++) cin>>f[i];

    for(int i=1;i<=m;i++)
    {
        cin>>p[i].b>>p[i].a>>p[i].c;
        p[i].b = f[p[i].b];
    }

    sort(p+1,p+1+m);
    memset(dp,-inf,sizeof(dp));dp[0] = 0;
//01背包
    for(int i=1;i<=m;i++)
        for(int j=T;j>=p[i].c;j--)
    {
        dp[j] = max(dp[j],dp[j-p[i].c]+p[i].a-j*p[i].b);
    }
    ll ans = -inf;
    for(int i=1;i<=T;i++) ans = max(ans,dp[i]);
    cout<<ans;


    return 0;
}