Cod sursa(job #1320454)

Utilizator sulzandreiandrei sulzandrei Data 17 ianuarie 2015 23:34:09
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.22 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

long long a,tmax,h[3000011],l,x,n,i,j,aux,N;

struct aaa{long long t,c;} t[200011];

void up(long long poz){
long long c,p;
c=poz;
p=c>>1;

   while(c!=1 && h[c] > h[p] ){
   aux=h[c];
   h[c]=h[p];
   h[p]=aux;

   c=p;
   p=c>>1;
   }


}

void down(long long poz){
long long c,p;
p=poz;
c=poz<<1;

   while(c<=N){

      if( h[c] < h[c+1] && c<N)c++;

      if(h[p]<h[c]){
      aux=h[c];
      h[c]=h[p];
      h[p]=aux;

      p=c;
      c=p<<1;
      }

      else
      break;

   }



}

int cmp(aaa a,aaa b){
return a.t>b.t;
}


int main(){

FILE *f=fopen("lupu.in","r");
fscanf(f,"%lld %lld %lld",&n,&x,&l);

  for(i=1;i<=n;i++){
  fscanf(f,"%lld %lld",&a,&t[i].c);
  t[i].t=(x-a)/l;
     if(t[i].t > tmax)
     tmax=t[i].t;
  }

fclose(f);

sort(t+1,t+n+1,cmp);
long long q=1;
long long S=0;
t[n+1].t=-1;

    for(i=tmax;i>=0;i--){

     while(t[q].t==i){
     N++;
     h[N]=t[q].c;
     up(N);
     q++;
     }

     if(N>=1){
     S+=h[1];
     h[1]=h[N];
     N--;
     down(1);
     }

    }

FILE *g=fopen("lupu.out","w");
fprintf(g,"%lld",S);
fclose(g);

return 0;
}