Pagini recente » Cod sursa (job #592830) | Cod sursa (job #111589) | Cod sursa (job #1824862) | Cod sursa (job #786631) | Cod sursa (job #149660)
Cod sursa(job #149660)
#include <stdio.h>
#define DIM 2001
struct inter {
long int t;
long int p;
};
typedef inter tip;
tip v[DIM];
int a[DIM];
int n,c,i,j,x,q,r,max,g;
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("carnati.in","r");
fscanf(f,"%d %d",&n,&c);
for (i=1;i<=n;i++)
fscanf(f,"%d %d",&v[i].t,&v[i].p);
fclose(f);
sort(v,n);
for (i=1;i<=n;i++) {
x = v[i].p;
a[1]=0;
if (v[1].p>=x)
if (x>c)
a[1]=x-c;
if (max<a[1])
max=a[1];
for (j=2;j<=n;j++) {
if (x>v[j].p) g=0;
else g=x;
q = a[j-1]-(v[j].t-v[j-1].t)*c+g;
r = g-c;
if (q>r)
a[j]=q;
else
a[j]=r;
if (a[j]>max)
max=a[j];
}
}
FILE *ff = fopen("carnati.out","w");
fprintf(ff,"%d",max);
fclose(ff);
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].t>v[p].t)) {
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].t>v[c].t))
c++;
if (v[c].t>v[p].t) {
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);
}
}