Pagini recente » Cod sursa (job #1102424) | Cod sursa (job #350498) | Cod sursa (job #3226261) | Cod sursa (job #2070382) | Cod sursa (job #632535)
Cod sursa(job #632535)
#include <stdio.h>
#define NMAX 100005
int N,heap[NMAX],moment[NMAX],noduri;//nr de noduri din heap
struct nod{
int puf,dist;
}oaia[NMAX];
int poz(int li, int ls){
int ii=1,jj=0,a;
nod aux;
while(li<ls){
if(moment[li]<moment[ls]){
aux=oaia[li];
oaia[li]=oaia[ls];
oaia[ls]=aux;
a=moment[li];
moment[li]=moment[ls];
moment[ls]=a;
a=ii;
ii=-jj;
jj=-a;
}
li+=ii;
ls+=jj;
}
return li;
}
void sort(int li, int ls){
if(li<ls){
int k;
k=poz(li,ls);
sort(li,k-1);
sort(k+1,ls);
}
}
void urca(int poz){
int x,aux;
while((x=poz/2)&&(oaia[heap[x]].puf<oaia[heap[poz]].puf)){
aux=heap[x];
heap[x]=heap[poz];
heap[poz]=aux;
poz=x;
}
}
void coboara_varful(){
int max,fiu,x=1,c=1;
do{
fiu=c;
//daca pot sa cobor prin stanga
if((x=2*c)>noduri)return;
if(oaia[heap[c]].puf<oaia[heap[x]].puf){max=oaia[heap[x]].puf;fiu=x;}
if(((++x)<=noduri) && (oaia[heap[x]].puf>max)){fiu=x;}
//interschimba c cu fiu
x=heap[c];
heap[c]=heap[fiu];
heap[fiu]=x;
c=fiu;
}while(fiu!=c);
}
void push(int ind){
noduri++;
heap[noduri]=ind;
urca(noduri);
}
void elimina_varf(){
heap[1]=heap[noduri];
noduri--;
//printf("sunt inainte de coboara\n");
coboara_varful();
//printf("sunt dupa coboara\n");
}
int main(){
int i,L,X,n,maxmom=-1;//momentul maxim/cate seturi de oi exista
int puf,dist;
FILE *fin=fopen("lupu.in","r");
FILE *fout=fopen("lupu.out","w");
fscanf(fin,"%d%d%d",&n,&X,&L);
for(i=1;i<=n;i++){
fscanf(fin,"%d%d",&dist,&puf);
if(X>=dist){
N++;
oaia[N].dist=dist;
oaia[N].puf=puf;
moment[N]=(X-oaia[N].dist)/L+1;
if(moment[N]>maxmom)maxmom=moment[N];
}
}
//sortez vectorul oaia[] dupa moment
sort(1,N);
int j=1;
long long suma=0;
noduri=0;
//printf("maxmom=%d\n",maxmom);
for(i=maxmom;i>=1;i--){
//printf("i=%d\n",i);
while(j<=N && moment[j]==i){
//adaug toate oile din acest set in heap (adaug doar indicele)
push(j);
j++;
}
if(noduri>=1){
suma+=oaia[heap[1]].puf;
elimina_varf();
}
}
fprintf(fout,"%lld\n",suma);
return 0;
}