记录编号	166588	评测结果	AAAAAAAAAA
题目名称	多人背包	最终得分	100
用户昵称	啊啦吧啦吧啦	是否通过	通过
代码语言	C++	运行时间	0.492 s
提交时间	2015-06-15 17:57:26	内存使用	1.33 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int k,v,n;
int f[51][5001];
int val[201],wei[201];
int q1[5001],q2[5001];

int main()
{
	freopen("bags.in","r",stdin);
	freopen("bags.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>k>>v>>n;
	for(int i=1;i<=k;i++)
		fill(f[i],f[i]+n+1,-0x7f);
	for(int i=1;i<=n;i++)
		cin>>wei[i]>>val[i];
	f[1][0]=0;
 	for(int i=1;i<=n;i++)  
	{
		for(int j=v;j>=wei[i];j--)
		{
			for(int p=1;p<=k;p++)
			{
				q1[p]=f[p][j];
				q2[p]=f[p][j-wei[i]]+val[i];
			}
			int c1=1,c2=1,tot=0;
			while(tot<k)
			{
				if(q1[c1]>q2[c2])
				f[++tot][j]=q1[c1++];
				else
				f[++tot][j]=q2[c2++];
			}
			
		}
	}
	int ans=0;
	for(int i=1;i<=k;i++)
	ans+=f[i][v];
	
	cout<<ans;
 return 0;
}