美味菜肴

还是被坑了，注意菜的种类是m！！！
01背包，但注意再想想，的是，区别背包与顺序无关，这个有关。那么就找个合理的顺序。
假设i,j交换更优
ai - bi * ci + aj - bj * (ci + cj) < aj - bj *cj + ai - bi * (ci +cj )
- bj * ci < -bi * cj
bj * ci > bi * cj
排个序就行。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f;
const int maxn=2e6+9;
int t,n,m;
int f[maxn],a[maxn];
struct nod{
    int cnt,a,c;
}node[maxn];
bool cmp(nod i,nod j)
{
    return i.c*a[j.cnt]<j.c*a[i.cnt];
}
signed main()
{
    cin>>n>>m>>t;
    memset(f,-inf,sizeof(f));
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
    {
        cin>>node[i].cnt>>node[i].a>>node[i].c;
    }
    sort(node+1,node+1+m,cmp);
    f[0]=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=t;j>=node[i].c;j--)
            f[j]=max(f[j],f[j-node[i].c]+node[i].a-j*a[node[i].cnt]);
    }
    int ans=-1e9;
    for(int i=1;i<=t;i++) ans=max(ans,f[i]);
    cout<<ans;
}