Cod sursa(job #337574)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 4 august 2009 10:48:14
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <stdio.h>
#define Nmax 120000
#define INF 2000000000
#define ll long long

int h[Nmax],poz[Nmax],d[Nmax],a[Nmax],t[Nmax];
int n,x,l,dh;
ll sum;

void sort(int l,int r){
	int i,j,x,y;
   i=l; j=r; x=t[l+(r-l)/2];
   do{
   	while(t[i] > x) i++;
      while(x > t[j]) j--;
      if(i<=j){
      	y=t[i]; t[i]=t[j]; t[j]=y;
      	y=d[i]; d[i]=d[j]; d[j]=y;
      	y=a[i]; a[i]=a[j]; a[j]=y;
         i++; j--;
      }
   } while(i<=j);
   if(i<r) sort(i,r);
   if(l<j) sort(l,j);
}


void read(){
   int i;
	freopen("lupu.in","r",stdin);
   freopen("lupu.out","w",stdout);
   scanf("%d%d%d",&n,&x,&l);
   for(i=1;i<=n;++i) scanf("%d%d",&d[i],&a[i]);
   for(i=1;i<=n;++i)
   	if(d[i] > x) t[i]=-INF;
      else t[i]=(x-d[i])/l;
   sort(1,n);
//   for(i=1;i<=n;++i) poz[i]=i;
}

void swap(int i,int j){
	int aux=h[i]; h[i]=h[j];
   h[j]=aux;
   poz[h[i]]=i;
   poz[h[j]]=j;
}

void UP(int k){
	int tata=k/2;
   if(tata)
     if(a[h[k]] > a[h[tata]]){
     		swap(k,tata);
         UP(tata);
     }
}

void DOWN(int k){
	int st=2*k,dr=st+1,max=k;
   if(st<=dh && a[h[st]]>a[h[max]]) max=st;
   if(dr<=dh && a[h[dr]]>a[h[max]]) max=dr;
   if(max != k){
   	swap(k,max);
      DOWN(max);
   }
}

void work(){
	int i,j,pmin;
   j=1;
   for(i=t[1]; i>=0; --i){
       if(t[j] == i){
         while(t[j] == i && j<=n){
           ++dh;
           h[dh]=j;
           poz[dh]=dh;
           UP(poz[dh]);
           ++j;
         }
         // scot max
         if(dh){
         	swap(1,dh);
         	dh--;
         	DOWN(1);
         	pmin=h[dh+1];
         	sum += a[pmin];
         }
       }
       else
       if(dh){
            // scot max
         	swap(1,dh);
         	dh--;
         	DOWN(1);
         	pmin=h[dh+1];
         	sum += a[pmin];
         }

   }
   printf("%lld\n",sum);
   fclose(stdin); fclose(stdout);
}

int main(){
	read();
   work();
   return 0;
}