C++14(g++5.4) 解法, 执行用时: 16ms, 内存消耗: 8292K, 提交时间: 2020-06-18 08:33:18

using namespace std;
#include <bits/stdc++.h>
#define int long long
int s[55];
struct node {
	int id,a,c;
	bool operator < (const node p) const
	{
		return s[p.id]*c<s[id]*p.c;
	}
}mp[55];
int dp[1000005];
signed main (void)
{
	int n,m,t;
	cin>>n>>m>>t;
	for (int i=1;i<=n;i++)
	    cin>>s[i];
	for (int i=0;i<m;i++)
	    cin>>mp[i].id>>mp[i].a>>mp[i].c;
	sort (mp,mp+m);
	memset (dp,-0x3f,sizeof dp);
	dp[0]=0;int ans=-1e18;
	for (int i=0;i<m;i++)
	{
		for (int j=t;j>=mp[i].c;j--)
		{
			dp[j]=max(dp[j],dp[j-mp[i].c]+mp[i].a-s[mp[i].id]*j);
			ans=max(ans,dp[j]);
		}
	}
	cout<<ans<<'\n';
}

C++ 解法, 执行用时: 9ms, 内存消耗: 1172K, 提交时间: 2022-03-18 00:00:03

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,t;
struct ee
{
	ll a,b,c;
}e[60];
ll d[60];
ll dp[1000010];
bool cmp(ee a,ee b)
{
	return d[a.a]*b.c>d[b.a]*a.c;
}
int main()
{
	cin>>n>>m>>t;
	ll i,j,ans=-(ll)1e18;
	fill(dp+1,dp+1+t,-(ll)1e18);
	dp[0]=0;
	for (i=1;i<=n;i++) cin>>d[i];
	for (i=1;i<=m;i++) cin>>e[i].a>>e[i].b>>e[i].c;
	sort(e+1,e+1+m,cmp);
	for (i=1;i<=m;i++)
	{
		for (j=t;j>=e[i].c;j--)
		{
			dp[j]=max(dp[j],dp[j-e[i].c]+e[i].b-d[e[i].a]*j);
			ans=max(ans,dp[j]);
		}
	}
	cout<<ans<<endl;
	return 0;
}

pypy3 解法, 执行用时: 152ms, 内存消耗: 38484K, 提交时间: 2021-06-01 15:14:54

import math

n, m, T = inputs = map(int, input().split())
b = list(map(int, input().split()))
a = []
for _ in range(m):
	j, x, y = map(int, input().split())
	a.append((b[j - 1], x, y))
a.sort(key=lambda x: x[2] / x[0])
ans = -math.inf
dp = [-math.inf] * (T + 1)
dp[0] = 0
for x, y, z in a:
	for t in range(T, z - 1, -1):
		dp[t] = max(dp[t], dp[t - z] + y - t * x)
		ans = max(ans, dp[t])
print(ans)