Cod sursa(job #322589)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 9 iunie 2009 12:02:40
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
struct sec{long t,c;}a[5000];
long n,c,i,x,g,a1,a2,ii,m;
long cmp(sec a,sec b)
{if(a.t<b.t)return 1;
 return 0;}
int main()
{
 freopen("carnati.in","r",stdin);
 freopen("carnati.out","w",stdout);
 scanf("%ld%ld",&n,&c);
 for(i=1;i<=n;++i)
    scanf("%ld%ld",&a[i].t,&a[i].c);
 sort(a+1,a+n+1,cmp);
 a[0].t=a[0].c=-10000;
 for(x=a[1].c,ii=1;ii<=n;++ii,x=a[ii].c)
 {a2=-10000;
  for(i=1;i<=n;++i)
     {if(a[i].c>=x)g=x;
             else g=0;
      a1=a2-(a[i].t-a[i-1].t)*c+g;
      if(a1<g-c)a1=g-c;
      a2=a1;
      if(a1>m)m=a1;}}
 printf("%ld\n",m);
 return 0;
}