比赛 |
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();
}