Cod sursa(job #196595)

Utilizator alexeiIacob Radu alexei Data 27 iunie 2008 13:58:05
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define nmax 2024

typedef struct{
        int cost,timp;
        }q;
q v[nmax];

inline int cmp(q A,q B)
{
      return A.timp<B.timp;
}

inline int max(const int a,const int b)
{
       if( a>b )
       return a;
       return b;
}

int main(){

freopen("carnati.in","r",stdin);
freopen("carnati.out","w",stdout);

int N,U;
scanf("%d%d",&N,&U);

int i,j;
int a1,a2;

for(i=1,j=0; i<=N; ++i)
{
             scanf("%d%d",&a1,&a2);
             if( a2>U )
             {
             v[++j].timp=a1;
             v[j].cost=a2;
             }
}

N=j;

sort(v+1,v+1+N,cmp);

int sum,solfin=0,timp,tsol;
int sol,aux;

v[0].timp=0;

for(i=1; i<=N; ++i)
{         
         tsol=v[i].cost;
         sol=0;
         
         for(j=1; j<=N; ++j)
         {
                  
         if( v[j].cost<tsol )
             a2=0;
         else
             a2=tsol;
          
          aux=sol+a2-(v[j].timp-v[j-1].timp)*U;
          
          aux=max( aux, a2-U );
          
          solfin=max( aux, solfin );
   
          sol=aux;
         }  

}                 
printf("%d\n",solfin);

return 0;
}