Cod sursa(job #149660)

Utilizator marinMari n marin Data 5 martie 2008 22:46:21
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#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);
  }
}