Pagini recente » Cod sursa (job #2862936) | Cod sursa (job #1243003) | Cod sursa (job #2402631) | Cod sursa (job #2223650) | Cod sursa (job #328731)
Cod sursa(job #328731)
#include <stdio.h>
#define Nmax 2005
struct om{
long t,p;
};
om a[Nmax];
long best[Nmax];
long n,i,j,c,rez;
long MAX(long x,long y){
return x > y ? x : y;
}
void incearca(long pfix){
long i;
if (a[1].p>=pfix)best[1]=pfix-c; else best[1]=0;
rez=best[1];
for(i=2;i<=n;++i){
if(a[i].p>=pfix)
best[i]=MAX(pfix-c,best[i-1] - (a[i].t-a[i-1].t)*c + pfix);
else best[i]=best[i-1] - (a[i].t-a[i-1].t)*c;
if(best[i] > rez) rez=best[i];
}
}
void sort(long l,long r){
long i,j,x,y;
i=l; j=r; x=a[l+(r-l)/2].t;
do{
while(a[i].t < x) i++;
while(x < a[j].t) j--;
if(i<=j){
y=a[i].t; a[i].t=a[j].t; a[j].t=y;
y=a[i].p; a[i].p=a[j].p; a[j].p=y;
++i; --j;
}
} while(i<=j);
if(i<r) sort(i,r);
if(l<j) sort(l,j);
}
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].p);
sort(1,n);
// a[0].t=best[0]=-10;
for(i=1;i<=n;++i)
incearca(a[i].p);
if(rez>0)printf("%ld\n",rez);
else printf("0\n");
fclose(stdin); fclose(stdout);
return 0;
}