记录编号	549630	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2019J]纪念品	最终得分	100
用户昵称	夜莺	是否通过	通过
代码语言	C++	运行时间	0.403 s
提交时间	2020-02-19 13:34:58	内存使用	9.67 MiB

#include<cstdio>
using namespace std;
typedef long long ll;
const int MAXN=101,MAXM=10001;
ll price[MAXN][MAXM];
ll t,n,m;
int main(){
	freopen("csp2019pj_souvenir.in","r",stdin);
	freopen("csp2019pj_souvenir.out","w",stdout);
	scanf("%lld%lld%lld",&t,&n,&m);
	for(int i=1;i<=t;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&price[i][j]);
	for(int k=2;k<=t;k++){
		int dp[MAXM]={0};
		int MAX=0;
		for(int i=1;i<=n;i++)
			for(int j=price[k-1][i];j<=m;j++){
				dp[j]=dp[j]>dp[j-price[k-1][i]]+price[k][i]-price[k-1][i]?dp[j]:dp[j-price[k-1][i]]+price[k][i]-price[k-1][i];
				MAX=MAX>dp[j]?MAX:dp[j];
			}
		m+=MAX;
	}
	printf("%lld",m);
	return 0;
}