Cod sursa(job #769400)

Utilizator valentina506Moraru Valentina valentina506 Data 19 iulie 2012 11:10:34
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include<fstream>
#include<algorithm>
using namespace std;
int n,m,i,j,maxim,maxc;
struct oras
{
	int d,l;
};
oras a[50001];
int cmp(oras a, oras b)
{
	if(a.d==b.d)
		return a.l<b.l;
	return a.d<b.d;
}

int main()
{
	freopen("orase.in","r",stdin);
	freopen("orase.out","w",stdout);
	
	scanf("%d%d",&m,&n);
	for(i=1;i<=n;++i)
		scanf("%d%d",&a[i].d,&a[i].l);
	
	sort(a+1,a+n+1,cmp);
	maxim=maxc=a[1].l+a[2].l+a[2].d-a[1].d;
	for(i=3;i<=n;++i)
	{
		maxc=max(a[i-1].l,maxc-a[i-1].l)+a[i].l+a[i].d-a[i-1].d;
		maxim=max(maxim,maxc);
	}
	
	printf("%d\n",maxim);
	
	return 0;
}