Cod sursa(job #420004)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 18 martie 2010 12:29:51
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE*f=fopen("orase.in","r");
FILE*g=fopen("orase.out","w");
int maxim (int a, int b){
	if(b>a)
		a=b;
	return a;
}

struct newType{
	int d;
	int l;
};
newType v[50001];
int m,n,i,Sol;
int dmax[50001];

int cmp(newType a,newType b){
	return a.d<b.d;
}
int main () {
	fscanf(f,"%d %d",&m,&n);
	for(i=1;i<=n;i++){
		fscanf(f,"%d %d",&v[i].d,&v[i].l);
	}
	sort(v+1,v+n+1,cmp);
	
	
	dmax[1]=0;
	for(i=2;i<=n;i++){
		dmax[i]=maxim(v[i-1].l,dmax[i-1])+v[i].d-v[i-1].d;
		if (dmax[i]+v[i].l>Sol)
			Sol = dmax[i]+v[i].l;
	}
	fprintf(g,"%d",Sol);
	
	
	
	fclose(f);
	fclose(g);
	return 0;
}