Cod sursa(job #431720)

Utilizator eukristianCristian L. eukristian Data 1 aprilie 2010 12:36:29
Problema Orase Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>

using namespace std;

ifstream f("orase.in");ofstream g("orase.out");
int M,N,L[50001],D[50001],dist[50001];

void read_data();
void solve();
void sort();

int main()
{
	read_data();
	solve();
	return 0;
}

void read_data()
{
	f >> M >> N;
	for (int i = 1;i <= N; ++i)
		f >> D[i] >> L[i];
}

void solve()
{
	sort();

	int max = 0,max_cautat = 0;
	for (int i = 2 ; i <= N ; ++i)
	{
		max = max + D[i] - D[i - 1];
		if (D[i] - D[i - 1] + L[i - 1] > max)
			max = D[i] - D[i - 1] + L[i - 1];
		dist[i] =  max;
		if (max + L[i] > max_cautat)
			max_cautat = max + L[i];
	}
	g << max_cautat << endl;
}

void sort()
{
	int cl,cd,j;
	for (int i = 2 ; i <= N ; ++i)
	{
		cl = L[i];
		cd = D[i];
		for (j = i - 1 ; cd < D[j] && j > 0 ; --j)
		{
			D[j + 1] = D[j];
			L[j + 1] = L[j];
		}
		L[j + 1] = cl;
		D[j + 1] = cd;
	}
}