Cod sursa(job #542579)

Utilizator marinutzacatana marina marinutza Data 26 februarie 2011 15:52:40
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int m,n,i,sum,maxim;
struct strada
{
	int d;
	int l;
};
strada x[50010];
bool comp(strada a,strada b)
{
	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",&x[i].d,&x[i].l);
	}
	sort(x+1,x+n+1,comp);
	maxim=sum=x[1].l+x[2].d-x[1].d+x[2].l;
	for(i=2;i<=n;i++)
	{
		if(sum-x[i].l+x[i+1].d-x[i].d+x[i+1].l<x[i].l+x[i+1].d-x[i].d+x[i+1].l)
		{
			sum=x[i].l+x[i+1].d-x[i].d+x[i+1].l;
		}
		else
		{
			sum=sum-x[i].l+x[i+1].d-x[i].d+x[i+1].l;
		}
		if(maxim<sum)
		{
			maxim=sum;
		}
	}
	printf("%d",maxim);
	return 0;
}