Pagini recente » Cod sursa (job #2981412) | Cod sursa (job #2233608) | Cod sursa (job #1463665) | Cod sursa (job #3244432) | Cod sursa (job #68370)
Cod sursa(job #68370)
#include <stdio.h>
#define nmax 3267
int i, j, k, l, N, M;
long long dmax, max;
long long P[nmax], V[nmax], X[nmax], Y[nmax];
void msort(int l, int r)
{
if (l >= r)
return;
int m = (l+r) >> 1;
msort(l, m);
msort(m+1, r);
for (i = k = l, j = m+1; i <= m && j <= r;)
if (P[i] <= P[j])
{
X[k] = V[i];
Y[k++] = P[i++];
}
else
{
X[k] = V[j];
Y[k++] = P[j++];
}
while (i <= m)
{
X[k] = V[i];
Y[k++] = P[i++];
}
while (j <= r)
{
X[k] = V[j];
Y[k++] = P[j++];
}
for (i = l; i <= r; i++)
{
V[i] = X[i];
P[i] = Y[i];
}
}
int main(void)
{
freopen("orase.in", "r", stdin);
freopen("orase.out", "w", stdout);
scanf("%d%d", &M, &N);
for (i = 1; i <= N; i++)
scanf("%d%d", &P[i], &V[i]);
msort(1, N);
dmax = V[1];
for (i = 2; i <= N; i++)
{
if (V[i] + dmax + P[i]-P[i-1] > max)
max = V[i] + dmax + P[i]-P[i-1];
dmax = dmax + P[i]-P[i-1];
if (V[i] > dmax)
dmax = V[i];
}
printf("%Ld\n", max);
return 0;
}