比赛 20100913 评测结果 AAAAAAWAAA
题目名称 越狱 最终得分 90
用户昵称 Citron酱 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-09-13 21:26:23
显示代码纯文本
#include <fstream>

#define I_F "prisonbreak.in"
#define O_F "prisonbreak.out"
#define MAX 10001

using namespace std;

int n;
long s[MAX],d[MAX];
short o[MAX];
long l,p;

void Input();
void Exchange(int a, int b);
void Qsort(int l, int r);
void Dyna();
void Output();

int main()
{
	Input();
	Qsort(1,n);
	Dyna();
	Output();
	return 0;
}

void Input()
{
	int i;
	ifstream fin(I_F);
	fin>>n;
	for (i=1; i<=n; fin>>s[i]>>o[i++]);
	fin>>l>>p;
	fin.close();
}

void Exchange(int a, int b)
{
	long t=s[a];
	s[a]=s[b];
	s[b]=t;
	t=o[a];
	o[a]=o[b];
	o[b]=t;
}

void Qsort(int l, int r)
{
	long x=s[l+rand()%(r-l+1)];
	int i=l, j=r;
	do
	{
		while (s[i]>x) i++;
		while (s[j]<x) j--;
		if (i<=j)
			Exchange(i++,j--);
	} while (i<j);
	if (i<r)
		Qsort(i,r);
	if (l<j)
		Qsort(l,j);
}

void Dyna()
{
	int i,j;
	for (i=1; i<=n; s[i]=l-s[i++]);
	d[0]=p;
	
	for (i=1; i<=n; i++)
		for (j=i; j>=0; j--)
			if (d[j-1]>=s[i])
				d[j]=max(d[j],d[j-1]+o[i]);
}

void Output()
{
	bool f=true;
	ofstream fout(O_F);
	for (int i=0; i<=n; i++)
		if (d[i]>=l)
		{
			fout<<i<<endl;
			f=false;
			break;
		}
	if (f)
		fout<<"-1\n";
	fout.close();
}