Pagini recente » Cod sursa (job #2552918) | Cod sursa (job #2525857) | Cod sursa (job #1676376) | Cod sursa (job #1578403) | Cod sursa (job #142716)
Cod sursa(job #142716)
#include <stdio.h>
#include <string.h>
#define fin "carnati.in"
#define fout "carnati.out"
const int Nmax = 2010;
struct inf
{
int timp,cst;
};
int N,C;
inf v[Nmax];
long long best,a[Nmax];
inline long long max(long long a,long long b) { return (a>b)?(a):(b); }
void quicksort(int st,int dr)
{
int m,i,j;
inf aux;
m = (st + dr) / 2;
i = st; j = dr;
do
{
while ( v[i].timp < v[m].timp ) ++i;
while ( v[j].timp > v[m].timp ) --j;
if ( i <= j )
{
aux = v[i];
v[i] = v[j];
v[j] = aux;
++i;
--j;
}
} while ( i < j );
if ( i < dr ) quicksort(i,dr);
if ( j > st ) quicksort(st,j);
}
void readsolve()
{
int i,j,k,X;
long long val;
freopen(fin,"r",stdin);
freopen(fout,"w",stdout);
scanf("%d%d",&N,&C);
for ( i = 1; i <= N; ++i )
scanf("%d%d",&v[i].timp,&v[i].cst);
quicksort(1,N);
best = v[1].cst - C;
v[0].timp = v[1].timp - 1;
v[N+1].timp = -2;
for ( i = 1; i <= N; ++i )
{
X = v[i].cst;
memset(a,0,sizeof(a));
for ( j = 1; j <= N; ++j )
{
val = 0;
for ( k = j; v[k].timp == v[j].timp; ++k)
if ( X <= v[k].cst )
val += X;
--k;
a[k] = max( a[j-1] - ( v[j].timp - v[j-1].timp ) * C + val,val-C);
best = max(best,a[k]);
j = k;
}
}
printf("%lld\n",best);
}
int main()
{
readsolve();
return 0;
}