Pagini recente » Cod sursa (job #1048715) | Cod sursa (job #2693517) | Cod sursa (job #2368174) | Cod sursa (job #2836803) | Cod sursa (job #619646)
Cod sursa(job #619646)
#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;
}