Cod sursa(job #68371)

Utilizator vmaneavmanea vmanea Data 27 iunie 2007 17:45:03
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <stdio.h>

#define nmax 50005

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("%Ld%Ld", &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;
}