Pagini recente » Cod sursa (job #290495) | Cod sursa (job #309847) | Cod sursa (job #2583336) | Cod sursa (job #636506) | Cod sursa (job #150265)
Cod sursa(job #150265)
#include <stdio.h>
#define DIM 2001
struct inter {
long int l;
long int d;
};
typedef inter tip;
tip v[DIM];
int a[DIM];
int n,c,i,m,max;
void cre(tip *v, long int n);
void corect(long int poz, tip *v, long int n);
void sort(tip *v, long int n);
int main(){
FILE *f = fopen("orase.in","r");
fscanf(f,"%d %d",&m,&n);
for (i=1;i<=n;i++)
fscanf(f,"%d %d",&v[i].d,&v[i].l);
fclose(f);
sort(v,n);
a[1]=v[1].d;
for (i=2;i<=n;i++) {
if (a[i-1]>v[i-1].l)
a[i]=a[i-1];
else
a[i]=v[i-1].l;
a[i]=a[i]+v[i].d-v[i-1].d;
}
max = 0;
for (i=1;i<=n;i++)
if (a[i]+v[i].l>max)
max=a[i]+v[i].l;
FILE *g = fopen("orase.out","w");
fprintf(g,"%d",max);
fclose(g);
return 0;
}
void cre(tip *v, long int n){
long int i,c,p;
tip aux;
for (i=2;i<=n;i++) {
c = i;
p = i>>1;
while ((p)&&(v[c].d>v[p].d)) {
aux = v[c];
v[c] = v[p];
v[p] = aux;
c = p;
p = p>>1;
}
}
}
void corect(long int poz, tip *v, long int n){
long int p,c;
tip aux;
p = poz;
c = p<<1;
while (c<=n) {
if ((c+1<=n) && (v[c+1].d>v[c].d))
c++;
if (v[c].d>v[p].d) {
aux = v[c];
v[c] = v[p];
v[p] = aux;
p = c;
c = p<<1;
} else break;
}
}
void sort(tip *v, long int n) {
long int i;
tip aux;
cre(v,n);
for (i=n;i>1;i--) {
aux = v[1];
v[1] = v[i];
v[i] = aux;
corect(1,v,i-1);
}
}