Cod sursa(job #139175)

Utilizator FlorianFlorian Marcu Florian Data 19 februarie 2008 19:50:08
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<stdio.h>
#include<stdlib.h>
FILE*f=fopen("carnati.in","r");
FILE*g=fopen("carnati.out","w");
typedef struct{
   int p,t;
   }Client;
int n,c,pret;
Client x[2004],a[2002];
long long max;
int cmp(const void*a, const void*b)
    {
    return x[*(int*)a].t-x[*(int*)b].t;
    }
void read()
  {
  fscanf(f,"%d %d",&n,&c);
  int i;
  int h[2003];
  for(i=1;i<=n;++i)
        {
        fscanf(f,"%d %d",&x[i].t,&x[i].p);
        h[i]=i;
        }
  qsort(h,n+1,sizeof(int),cmp);
  for(i=1;i<=n;++i) a[i]=x[h[i]];
  }
void solve()
  {
  int i,j,G;
  long long old,news;
  for(i=1;i<=n;++i)
     {
     old=0;
     for(j=1;j<=n;++j)
       {

       if(a[j].p>=a[i].p) G=a[i].p;

       else G=0;

       news=old-(a[j].t-a[j-1].t)*c+G;

       if(news<G-c) news=G-c;

       if(news>max) max=news;
       old=news;
       }

     }
  }
int main()
  {
  read();
  solve();
  fprintf(g,"%lld\n",max);
  return 0;
  }