Cod sursa(job #658517)

Utilizator CS-meStanca Marian Ciprian CS-me Data 8 ianuarie 2012 23:17:20
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *fin=fopen("orase.in","r");
FILE *fout=fopen("orase.out","w");
int n,m,mx,sol,i;

struct strada{
    int l,d;
};

strada s[50010];

int cmp(strada a, strada b){
	if(a.d==b.d){
        return a.l<b.l;
	}
	return a.d<b.d;
}

int main(){

	fscanf(fin,"%d %d",&m,&n);

	for(i=1;i<=n;i++){
		fscanf(fin,"%d %d",&s[i].d, &s[i].l);
    }

	sort(s+1,s+n+1,cmp);
	mx=0;
	sol=0;

	for(i=1;i<=n;i++){
		mx+=(s[i].d - s[i-1].d);

		if(mx+s[i].l>sol){
			sol=mx+s[i].l;
		}
		if(s[i].l>mx){
			mx=s[i].l;
		}
	}
	fprintf(fout,"%d",sol);

return 0;
}