Cod sursa(job #729382)

Utilizator robertpoeRobert Poenaru robertpoe Data 29 martie 2012 15:58:46
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.54 kb
#include<fstream>
#include<algorithm>
#define dim 60000
using namespace std;
ifstream f("orase.in");
ofstream g("orase.out");
struct city
{
	int x,c;
};city a[dim];
inline int comp(city a, city b)
{
	return (a.x<b.x);
}
int n,i,cost;
int max1,p,m;
void solve()
{
	max1=cost=a[1].c+a[2].c+a[2].x-a[1].x;
	for (i=3;i<=n;i++)
	{
		cost=max(a[i-1].c,cost-a[i-1].c)+a[i].c+a[i].x-a[i-1].x;
		if (cost>max1) 
			max1=cost;
	}
}
int main()
{
	f>>m>>n;
	for (i=1;i<=n;i++)
		f>>a[i].x>>a[i].c;
	sort(a+1,a+n+1,comp);
	solve();
	g<<max1;
	return 0;
}