记录编号	250823	评测结果	AAAAAAAAAA
题目名称	采药(加强版)	最终得分	100
用户昵称	dateri	是否通过	通过
代码语言	C++	运行时间	0.602 s
提交时间	2016-04-16 00:16:52	内存使用	1.90 MiB

#include<stdio.h>
int _w[500]={0},_v[500]={0},w[250500]={0},v[250500]={0},c[250500]={0},f[500]={0};
int asd()
{
	freopen("crazytime.in","r",stdin);
	freopen("crazytime.out","w",stdout);
	int n,i,j,k,l,m,count=0,flag,x,y,t;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
	  scanf("%d%d",&x,&y);
	  flag=1;
	  for(j=1;j<=count;j++)
	    if(_w[j]==x&&_v[j]==y)
	    {
		     c[j]++;
		     flag=0;
		     break;
		}
	  if(flag)
	  {
	    _w[++count]=x;
	    _v[count]=y;
	    c[count]=1;
	  }
    }
    int ok=0;
    for(i=1;i<=count;i++)
    {
    	t=1;
    	while(c[i]>t)
    	{
    		w[++ok]=_w[i]*t;
    		v[ok]=_v[i]*t;
    		c[i]-=t;
    		t*=2;
		}
		if(c[i]==0)
		  continue;
		w[++ok]=_w[i]*c[i];
    	v[ok]=_v[i]*c[i];
	}
	for(i=1;i<=ok;i++)
	  for(j=m;j>=w[i];j--)
	    if(f[j]<f[j-w[i]]+v[i])
	      f[j]=f[j-w[i]]+v[i];
	printf("%d",f[m]);
    return 0;
}
int asdd=asd();
int main(){;}