记录编号	20145	评测结果	AAAAAAAAAA
题目名称	罪犯问题B	最终得分	100
用户昵称	Citron酱	是否通过	通过
代码语言	C++	运行时间	0.139 s
提交时间	2010-10-21 07:38:20	内存使用	0.27 MiB

#include <fstream>

#define I_F "criminalb.in"
#define O_F "criminalb.out"

using namespace std;

int n,m,k;
long a,b,mx;
int x[1001];
int s[1001][2];

int min(int a, int b);
void Input();
void Clear_arr(int s[50001]);
int max(int a, int b);
void Dyna();
void Output();

int main()
{
	Input();
	Dyna();
	Output();
}

int min(int a, int b)
{
	if (a<b)
		return a;
	else
		return b;
}

void Input()
{
	ifstream fin(I_F);
	fin>>n>>m>>k;
	int i,t;
	for (i=1; i<=n; i++)
	{
		fin>>x[i];
		mx+=x[i];
	}
	for (i=0; i<m; i++)
	{
		fin>>t;
		if (t>0)
			s[t][0]++;
		else
			s[-t][1]++;
	}
	fin.close();
	for (i=1; i<=n; i++)
	{
		t=min(s[i][0],s[i][1]);
		k-=t;
		s[i][0]-=t;
		s[i][1]-=t;
	}
}

void Clear_arr(int s[50001])
{
	for (int i=0; i<50002; s[i++]=0);
}

int max(int a, int b)
{
	if (a>b)
		return a;
	else
		return b;
}

void Dyna()
{
	int f[50001];
	int i,j;
	
	Clear_arr(f);
	for (i=1; i<=n; i++)
		for (j=k; j>=0; j--)
			if (s[i][1]<=j)
				f[j]=max(f[j],f[j-s[i][1]]+x[i]);
	a=f[k];
	
	Clear_arr(f);
	for (i=1; i<=n; i++)
		for (j=k; j>=0; j--)
			if (s[i][0]<=j)
				f[j]=max(f[j],f[j-s[i][0]]+x[i]);
	b=mx-f[k];
}

void Output()
{
	ofstream fout(O_F);
	fout<<a<<'\n'<<b<<'\n';
	fout.close();
}