Pagini recente » Cod sursa (job #3263644) | Cod sursa (job #2637245) | Cod sursa (job #367155) | Cod sursa (job #1513224) | Cod sursa (job #142723)
Cod sursa(job #142723)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,C,best;
vector < pair<int,int> > v;
int main()
{
int i,j,x,y,minv,sum,a,p;
freopen("carnati.in","r",stdin);
freopen("carnati.out","w",stdout);
scanf("%d%d",&N,&C);
minv = 100000000;
for ( i = 1; i <= N; ++i )
{
scanf("%d%d",&x,&y),v.push_back(make_pair(x,y));
if ( x < minv ) minv = x;
}
v.push_back(make_pair(minv-1,0));
sort(v.begin(),v.end());
best = v[0].second - C;
for ( i = 1; i <= N; ++i )
{
sum = 0; a = 0; p = 0;
for ( j = 1; j <= N; ++j )
{
sum = sum - ( v[j].first - v[j-1].first ) * C + v[i].second * ( ( v[i].second <= v[j].second ) ? (1) : (0) );
if ( p != 0 )
best = max(best,sum-a+(v[p+1].first-v[p].first-1)*C);
else
best = max(best,sum);
if ( sum < a )
a = sum,p=j;
}
}
printf("%d\n",best);
return 0;
}