蒟蒻太xun

题目

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int m,n,dp[100001],ans;
struct node{int a,b,t;}kkk[100001];
bool cmp(node a,node b){a.t*a.b<b.t*b.b;}
signed main()
{
	scanf("%lld%lld",&m,&n);
	for(int i=1;i<=n;i++) scanf("%lld",&kkk[i].a);
	for(int i=1;i<=n;i++) scanf("%lld",&kkk[i].b);
	for(int i=1;i<=n;i++) scanf("%lld",&kkk[i].t);
	sort(kkk+1,kkk+n+1,cmp);
	for(int i=1;i<=n;i++)
		for(int j=m;j>=kkk[i].t;j--)
			dp[j]=max(dp[j],dp[j-kkk[i].t]+kkk[i].a-kkk[i].b*j);
	for(int i=1;i<=m;i++) ans=max(ans,dp[i]);
	printf("%lld\n",ans); 
	return 0;
}