Pagini recente » Cod sursa (job #1955624) | Cod sursa (job #1805177) | Cod sursa (job #168925) | Cod sursa (job #2233504) | Cod sursa (job #632595)
Cod sursa(job #632595)
#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;
max=oaia[heap[c]].puf;
//vecin in stanga
if((x=2*c)>noduri)return;
if(oaia[heap[x]].puf>max){
fiu=x;
max=oaia[heap[x]].puf;
}
if((x+=1)<=noduri && oaia[heap[x]].puf>max){
fiu=x;
}
//interschimb fiu cu c
max = heap[c];
heap[c] = heap[x];
heap[x] = max;
c=fiu;
}while(fiu!=c);
//cobor in fiul cel mai mic dintre cei doi
/*int aux, x, y = 0;
int loc=1;
while (loc != y){
y = loc;
if ((x=y*2)<=noduri && oaia[heap[loc]].puf<oaia[heap[x]].puf) loc = x;
x++;
if (x<=noduri && oaia[heap[loc]].puf<oaia[heap[x]].puf) loc = x;
aux = heap[loc];
heap[loc] = heap[y];
heap[y] = aux;
}*/
}
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;
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;
}
}
//sortez vectorul oaia[] dupa moment
sort(1,N);
int j=1;
long long suma=0;
noduri=0;
/*printf("maxmom=%d\n",moment[N]);
for(i=N;i>0;i--)printf("%d ",moment[i]);
printf("\n");*/
for(i=moment[1];i>=1;i--){
//printf("i=%d\n",i);
while(moment[j]==i){//nu trebuie sa verific sa nu ies din vector...e cpacit cu 0
//adaug toate oile din acest set in heap (adaug doar indicele)
//printf("adaug si %d la heap\n",j);
push(j);
j++;
}
//printf("urmatoarea serie\n");
if(noduri>=1){
suma+=oaia[heap[1]].puf;
elimina_varf();
}
}
fprintf(fout,"%lld\n",suma);
return 0;
}