Cod sursa(job #619646)

Utilizator ion824Ion Ureche ion824 Data 16 octombrie 2011 00:29:18
Problema Orase Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream>
using namespace std;
typedef struct{ int d,l; }oras;
oras a[50003],k; 

void quick_sort(int lb,int ub){
     int i=lb,j=ub; oras p=a[(i+j)>>1]; 
     do{                
        while(a[i].d<p.d ||(a[i].d==p.d && a[i].l<p.l))++i;
        while(a[j].d>p.d ||(a[j].d==p.d && a[j].l>p.l))--j;    
        if(i<=j){ k=a[i]; a[i]=a[j]; a[j]=k; ++i; --j; } 
     }while(i<=j);
     if(i<ub)quick_sort(i,ub);
     if(j>lb)quick_sort(lb,j); 
     }

int main(void){
    ifstream fin("orase.in");
    ofstream fout("orase.out");
    int m,n,i,suma=0,sum_max=0;
    fin>>m>>n;
    for(i=1;i<=n;++i)fin>>a[i].d>>a[i].l; fin.close();
    quick_sort(1,n);
    for(i=2;i<=n;++i){
      if(a[i].d-a[i-1].d+a[i].l+a[i-1].l>suma+a[i].l-a[i-1].l)
        suma=a[i].d-a[i-1].d+a[i].l+a[i-1].l;
      else
        suma=suma+a[i].l-a[i-1].l;
      if(suma>sum_max)sum_max=suma;
      }  
   fout<<sum_max; fout.close();
 return 0;   
}