Cod sursa(job #669806)

Utilizator maritimCristian Lambru maritim Data 27 ianuarie 2012 19:56:52
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<stdio.h>
#include<algorithm>
#include<fstream>
using namespace std;

ifstream f("orase.in");
ofstream g("orase.out");

typedef struct
{
	int x,y;
} xy;

#define MaxN 50100

int M,N,MAX;
xy A[MaxN];

void citire(void)
{
	f >> M >> N;
	for(int i=1;i<=N;i++)
		f >> A[i].x >> A[i].y;
}

int cmp(xy a, xy b)
{
	return a.x < b.x;
}

void Programare_Dinamica(void)
{
	int nr = A[1].y;
	
	for(int i=2;i<=N;i++)
	{
		nr += A[i].x-A[i-1].x;
		
		if(MAX < nr + A[i].y)
			MAX = nr+A[i].y;
		if(nr < A[i].y)
			nr = A[i].y;
	}
}

int main()
{
	citire();
	sort(A+1,A+N+1,cmp);
	Programare_Dinamica();
	
	g << MAX;
	
	return 0;
}