Cod sursa(job #420005)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 18 martie 2010 12:30:39
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

struct dist{
	int D;
	int L;
};

int n,m;
int i,j,sol;
int dmax[50001];

dist v[50001];

int comp(dist a, dist b){
	if(a.D != b.D)
		return a.D < b.D;
	else
		return a.L < b.L;
}

int maxim(int a, int b){
	if(a > b)
		return a;
	return b;
}

int main(){
	
	FILE *f1 = fopen("orase.in","r");
	fscanf(f1,"%d%d",&m,&n);
	for(i=1; i<=n; i++)
		fscanf(f1,"%d%d",&v[i].D,&v[i].L);	
	fclose(f1);
	
	sort(v+1,v+n+1,comp);
	
	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;		
	}
	
	
	FILE *f2 = fopen("orase.out","w");
	fprintf(f2,"%d",sol);
	fclose(f2);
	
	return 0;
}