Cod sursa(job #358885)

Utilizator prdianaProdan Diana prdiana Data 24 octombrie 2009 20:51:56
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int n,s,i,best;
struct drum
{
	int l,d;
};

vector<drum> v;

inline bool cmpf(const drum &v1,const drum &v2)
{
	return v1.d < v2.d;
}

int main()
{
	drum aux;
	freopen("orase.in","r",stdin);
	freopen("orase.out","w",stdout);

	scanf("%d%d",&n,&s);

	for (i=0;i<s;i++)
	{
		scanf("%d%d",&aux.d,&aux.l);
		v.push_back(aux);
	}
	sort(v.begin(),v.end(),cmpf);

	best = -1;

	drum lng;

	lng.l = v[0].l;
	lng.d = v[0].d;

	for (i=0;i<v.size();i++)
	{
		if (v[i].l+lng.l+(v[i].d-lng.d) > best)
		{
			best = v[i].l+lng.l+(v[i].d-lng.d);
		}

		if (v[i].l - v[i].d > lng.l - lng.d)
		{
			lng.l = v[i].l;
			lng.d = v[i].d;
		}
	}

	printf("%d",best);

	return 0;
}