记录编号 |
37453 |
评测结果 |
AAAAAAAAAA |
题目名称 |
越狱 |
最终得分 |
100 |
用户昵称 |
kaaala |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.608 s |
提交时间 |
2012-03-30 10:28:16 |
内存使用 |
0.42 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int oo=~0u>>1;
struct Node
{
int a,b;
}A[10010];
int N,L,P,f[2][10010],ans=oo;
bool operator <(Node a,Node b)
{
return a.a>b.a;
}
void dp()
{
bool fl=false;
for(int i=1;i<=N;i++)
{
fl=!fl;
memset(f[fl],-1,sizeof(f[fl]));
for(int j=0;j<=i&&j<ans;j++)
{
int tmp=f[!fl][j]-(A[i-1].a-A[i].a);
if(tmp>=0)
f[fl][j]=max(f[fl][j],tmp);
if(j)
{
tmp=f[!fl][j-1]-(A[i-1].a-A[i].a);
if(tmp>=0)
f[fl][j]=max(f[fl][j],tmp+A[i].b);
}
if(f[fl][j]-A[i].a>=0&&f[fl][j]<ans)
ans=j;
}
}
}
int main()
{
freopen("prisonbreak.in","r",stdin);
freopen("prisonbreak.out","w",stdout);
scanf("%d",&N);
for(int i=1;i<=N;i++)
scanf("%d%d",&A[i].a,&A[i].b);
scanf("%d%d",&L,&P);
A[0].a=L;
sort(A+1,A+1+N);
for(int i=1,tmp=P-(L-A[1].a);i<=N;i++)
if(tmp<0)
{
printf("-1\n");
return 0;
}
else
{
tmp-=A[i].a-A[i+1].a;
tmp+=A[i].b;
}
f[0][0]=P;
dp();
printf("%d\n",ans);
return 0;
}