Cod sursa(job #390630)

Utilizator bora_marianBora marian bora_marian Data 4 februarie 2010 10:59:55
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
# include <fstream>
using namespace std;
int n, m, d[50003], l[50003], dmax;

void read ()
{
	ifstream fin ("orase.in");
	fin>>m>>n;
	for (int i=1;i<=n;i++)
		fin>>d[i]>>l[i];
}

void qsort (int st, int dr)
{
	if (st<dr)
	{
		int i=st, j=dr, dd=0, aux;
		while (i<j)
		{
			if (d[i]>d[j])
			{
				aux=d[i];d[i]=d[j];d[j]=aux;
				aux=l[i];l[i]=l[j];l[j]=aux;
				dd=1-dd;
			}
			i+=dd;
			j-=1-dd;
		}
		qsort (st, i-1);
		qsort (i+1, dr);
	}
}

void solve ()
{
	int c, max, pm;
	pm=d[1];
	max=l[1];
	dmax=-1;
	for(int i=2;i<=n;i++)
	{
		c=l[i]+(d[i]-pm)+max;
		if (c>dmax)
			dmax=c;
		if (l[i]>max+(d[i]-pm))
			max=l[i], pm=d[i];
	}
}

int main ()
{
	read ();
	qsort (1, n);
	solve ();
	ofstream fout ("orase.out");
	fout<<dmax;
	return 0;
}