记录编号	144582	评测结果	AAAAAAAAAA
题目名称	[Vocaloid]Luka的章鱼丸子	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.203 s
提交时间	2014-12-24 12:19:29	内存使用	0.66 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[301][301]={0},zhi[301]={0},vi[301]={0},wi[301]={0},si[301]={0};
int i,j,k,l,m,n,p,zj1,zj2,zj3,zui=0,ans=0,V,S;
void init()
{
	scanf("%d%d%d%d",&n,&m,&V,&S);
	for(i=1;i<=n;i++)
	scanf("%d%d%d",&si[i],&vi[i],&wi[i]);
}
void prework()
{
	for(i=1;i<=m;i++)
	for(p=1;p<=V;p++)
	for(k=1;k<=n;k++)
	if(i>=si[k]&&p>=vi[k])
	{
		zj1=f[i-si[k]][p-vi[k]]+wi[k];
		if(f[i][p]<zj1)f[i][p]=zj1;
	}
	for(i=1;i<=m;i++)zhi[i]=f[i][V];
}
void work()
{
	memset(f,0,sizeof(f));
	zj1=m/S;
	for(i=1;i<=zj1;i++)
	{
		zj2=m-i*S;
		for(p=1;p<=zj2;p++)
		for(k=0;k<=p;k++)
		{
			zj3=f[i-1][k]+zhi[p-k];
			if(f[i][p]<zj3)f[i][p]=zj3;
		}
		if(f[i][zj2]>zui)
		{
			zui=f[i][zj2];
			ans=i;
		}
	}
}
int main()
{
	freopen("Luka.in","r",stdin);
	freopen("Luka.out","w",stdout);
	init();
	prework();
	work();
	printf("%d\n%d\n",zui,ans);
	return 0;
}