Poj Solution 2431

http://poj.org/problem?id=2431

#include<iostream>
#include"algorithm"
using namespace std;
const int size=10010;

struct stop
{
    int f,x;
}p[size];
int n,l,h;

bool cmp(stop a,stop b)
{
    return a.x>b.x;
}

void init()
{
    int i;

    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>p[i].x>>p[i].f;
    }
    cin>>l>>h;
    
    p[n+1].x=l;p[n+1].f=0;
    p[n].x=0;p[n].f=0;
    n+=2;
    std::sort(p,p+n,cmp);
    
    if(p[0].x!=l)
        while(1)
            cout<<"faint"<<endl;
}

int mem[2][size],down;
int *best=mem[0],*temp=mem[1];

void doit()
{
    int i,j,t;
    
    down=0;
    
    best[0]=h;
    for(i=1;i<n;i++)
    {
        for(j=down;j<=i;j++)
            temp[j]=-1;
        for(j=down;j<=i;j++)
        {
            if(j<i&&best[j]-(p[i-1].x-p[i].x)>temp[j])
                temp[j]=best[j]-(p[i-1].x-p[i].x);
            
            if(j>down && (t=best[j-1]-(p[i-1].x-p[i].x))>=0 && (t+=p[i].f) >temp[j])
                temp[j]=t;
            
            if(temp[j]<0)
                down=j+1;
        }
        std::swap(best,temp);
    }
}

int main()
{
    int i;
    init();
    doit();

    for(i=down;i<n-1;i++)
        if(best[i]>=0)break;
    if(i<n-1)
        cout<<i<<endl;
    else cout<<-1<<endl;

    return 0;
}