记录编号	20057	评测结果	AAAAAAAAAA
题目名称	罪犯问题B	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	1.295 s
提交时间	2010-10-20 09:23:20	内存使用	0.66 MiB

#include<iostream>

using namespace std;

int n,m,k,i,j,a[1010],b[1010],c[1010],d[2][50050],a1,a2,z;

int main()
{
	freopen("criminalb.in","r",stdin);
	freopen("criminalb.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=n;i++)
		scanf("%d",&c[i]);
	for(i=1;i<=m;i++)
	{
		scanf("%d",&z);
		if(z>0)
			a[z]++;
		else
			b[-z]++;
	}
	for(j=0;j<=k;j++)
		d[0][j]=d[1][j]=-2000000000;
	d[0][0]=0;
	for(i=1;i<=n;i++)
		for(j=0;j<=k;j++)
		{
			d[i%2][j]=-2000000000;
			if(b[i]<=j) 
				d[i%2][j]=d[(i+1)%2][j-b[i]]+c[i];
			if(a[i]<=j) 
				d[i%2][j]=max(d[i%2][j],d[(i+1)%2][j-a[i]]);
		}
	a1=-2000000000;
	for(i=0;i<=k;i++)
		if(d[n%2][i]>a1) 
			a1=d[n%2][i];
	printf("%d\n",a1);
	for(j=0;j<=k;j++)
		d[0][j]=d[1][j]=2000000000;
	d[0][0]=0;
	for(i=1;i<=n;i++)
		for(j=0;j<=k;j++)
		{
			d[i%2][j]=2000000000;
			if(b[i]<=j) 
				d[i%2][j]=d[(i+1)%2][j-b[i]]+c[i];
			if(a[i]<=j) 
				d[i%2][j]=min(d[i%2][j],d[(i+1)%2][j-a[i]]);
		}
	a2=2000000000;
	for(i=0;i<=k;i++)
		if(d[n%2][i]<a2) 
			a2=d[n%2][i];
	printf("%d\n",a2);
	return 0;
}