Poj Solution 2465

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

#include<iostream>
using namespace std;
inline int min(int a,int b)
{
    return a<b?a:b;
}

int dis[112],price[112];
int l,n;

void init()
{
    n=0;
    cin>>l;
    while(cin>>dis[n])
        cin>>price[n++];
    price[n]=99999999;
    dis[n]=l;
    n++;
}

int doit()
{
    int i,j,s,temp[212],p;
    int best[212];

    for(i=0;i<201;i++)
        best[i]=-1;
    best[100]=0;

    for(s=dis[0],i=0;i<n;i++)
    {
        for(j=0;j<201;j++)
            temp[j]=-1;
        for(j=s;j<201;j++)
            temp[j-s]=best[j];
        
        
        if(i<n-1)
        {
            p=-1;
            for(j=0;j<201;j++)
            {
                if(temp[j]>=0)
                {
                    if(p<0||p>temp[j])
                        p=temp[j];
                }

                if(p>=0&&(temp[j]<0||p<temp[j]))
                    temp[j]=p;
                if(p>=0)p+=price[i];
            }
        }

        for(j=0;j<201;j++)
            best[j]=temp[j];
        s=dis[i+1]-dis[i];
    }
    
    int ans=-1;

    for(j=100;j<201;j++)
        if(best[j]>=0&&(ans<0||best[j]<ans))
            ans=best[j];
    return ans;
}

int main()
{
    int ans;
    init();
    ans=doit();
    if(ans<0)
        cout<<"Impossible"<<endl;
    else cout<<ans<<endl;

    return 0;
}