比赛 20100913 评测结果 RRRRRRRRRR
题目名称 连续素数和 最终得分 0
用户昵称 Oo湼鞶oO 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-09-13 19:55:25
显示代码纯文本
#include <fstream>

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

using namespace std;

int n;
bool flag=true;
long s[MAX],d[MAX];
short o[MAX];
long l,p;

void Input();
void Dyna();
void Output();

int main()
{
	Input();
	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 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[n-j+1])
				if (j==i)
				{
					flag=false;
					break;
				}
				else
					d[j]=d[j-1]+o[n-j+1];
			else
				d[j]=max(d[j],d[j-1]+o[n-j+1]);
}

void Output()
{
	ofstream fout(O_F);
	if (flag)
	{
		for (int i=0; i<=n; i++)
			if (d[i]>=l)
			{
				fout<<i<<endl;
				break;
			}
	}
	else
		fout<<-1<<endl;
	fout.close();
}