Pagini recente » Cod sursa (job #1502162) | Cod sursa (job #807837) | Cod sursa (job #2615691) | Cod sursa (job #2678265) | Cod sursa (job #223416)
Cod sursa(job #223416)
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX_N 2005
struct client{int t, p;} V[MAX_N];
int N, C;
long long Bst[MAX_N], Max, M;
void citire()
{
scanf("%d %d",&N, &C);
for(int i = 1; i <= N; ++i)
scanf("%d %d",&V[i].t, &V[i].p);
}
struct cmp
{
bool operator()(const client a, const client b) const
{
return(a.t < b.t);
}
};
void solve()
{
sort(V+1, V+N+1, cmp());
Bst[0] = V[0].t = V[0].p = -10;
for(int i = 1; i <= N; ++i)
{
int X = V[i].p, lst = 0;
M = 0;
for(int i = 1; i <= N; ++i)
{
if(V[i].p < X) {Bst[i] = 0; continue;}
Bst[i] = X - C;
long long plus = (long long) M + X;
long long minus = (long long) C*(V[i].t - V[lst].t);
long long k = plus - minus;
if(k > Bst[i])
{
Bst[i] = k;
lst = i;
}
else
lst = i;
M = Bst[i];
if(M > Max)
Max = M;
}
}
printf("%lld\n", Max);
}
int main()
{
freopen("carnati.in","rt",stdin);
freopen("carnati.out","wt",stdout);
citire();
solve();
}