Pagini recente » Borderou de evaluare (job #145087) | Cod sursa (job #2529102) | Cod sursa (job #718494) | Cod sursa (job #1976810) | Cod sursa (job #196582)
Cod sursa(job #196582)
#include<stdio.h>
#include<algorithm>
using namespace std;
//bla bla bla
#define nmax 2024
typedef struct{
int cost,timp;
}q;
q v[nmax];
inline int cmp(q A,q B)
{
if( A.cost==B.cost )
return A.timp<B.timp;
return A.cost<B.cost;
}
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,a1,a2,a3=0;
for(i=1; i<=N; ++i){
scanf("%d%d",&a2,&a1);
if( a1>U ){
v[i-a3].cost=a1;
v[i-a3].timp=a2;}
else
++a3;
}
N-=a3;
sort(v+1,v+N+1,cmp);
int tmin,tmax,solfin=0,sum,sol;
int temp,aux=0,aux2,tcost;
int space;
for(i=1; i<=N; ++i)
{
tmin=tmax=v[i].timp;
tcost=v[i].cost;
sol=v[i].cost-U;
sum=1;
temp=1;
space=0;
for(j=i+1; j<=N; ++j)
{
aux=0;
if( v[j].timp > tmax )
aux=v[j].timp-tmax,space=1;
if( v[j].timp < tmin )
aux=tmin-v[j].timp,space=2;
aux2=(sum+1)*tcost-(temp+aux)*U;
if( aux2 > sol )
{
sol=aux2;
++sum;
temp+=aux;
if( space==1 )
tmax=v[j].timp;
else
if( space==2 )
tmin=v[j].timp;
}
space=0;
}
for(j=i-1; j>=1 && v[j].cost==tcost; --j)
{
aux=0;
if( v[j].timp > tmax )
aux=v[j].timp-tmax,space=1;
if( v[j].timp < tmin )
aux=tmin-v[j].timp,space=2;
aux2=(sum+1)*tcost-(temp+aux)*U;
if( aux2 > sol )
{
sol=aux2;
++sum;
temp+=aux;
if( space==1 )
tmax=v[j].timp;
else
if( space==2 )
tmin=v[j].timp;
}
space=0;
}
solfin=max(solfin,sol);
}
printf("%d\n",solfin);
return 0;
}