Pagini recente » Cod sursa (job #3181151) | Cod sursa (job #1222219) | Cod sursa (job #2682296) | Cod sursa (job #63673) | Cod sursa (job #1630126)
#include <stdio.h>
#include <algorithm>
#define lim 100005
using namespace std;
struct elem{int poz,val;};
elem v[lim];
int heap[lim],m;
int tata(int p){
return (p-1)/2;
}
int fiust(int p){
return 2*p+1;
}
int fiudr(int p){
return 2*p+2;
}
void schimba(int p,int q){
int aux;
aux=heap[p];
heap[p]=heap[q];
heap[q]=aux;
}
void urca(int p){
while(p>0&&heap[p]>heap[tata(p)]){
schimba(p,tata(p));
p=tata(p);
}
}
void adauga(int x){
heap[m]=x;
m++;
urca(m-1);
}
void coboara(int p){
int q,pp=1;
while(pp==1&&fiust(p)<m){
q=fiust(p);
if(fiudr(p)<m&&heap[fiust(p)]>heap[q])
q=fiudr(p);
if(heap[q]>heap[p]){
schimba(p,q);
p=q;
}
else
pp=0;
}
}
void sterge(int p){
m--;
schimba(m,p);
if(p>0&&heap[p]>heap[tata(p)])
urca(p);
else
coboara(p);
}
bool cmp(elem a,elem b){
if(a.poz<b.poz)
return true;
else
return false;
}
int main(){
FILE *fin,*fout;
fin=fopen("lupu.in","r");
fout=fopen("lupu.out","w");
int i,j,k,n,raza,x,rasp=0;
fscanf(fin,"%d%d%d",&n,&raza,&x);
for(i=1;i<=n;i++)
fscanf(fin,"%d%d",&v[i].poz,&v[i].val);
sort(v+1,v+n+1,cmp);
k=raza/x;
i=1;
for(j=k;j>=0;j--){
while(i<=n&&v[i].poz+j*x<=raza){
adauga(v[i].val);
i++;
}
if(m>0){
rasp+=heap[0];
sterge(0);
}
}
fprintf(fout,"%d",rasp);
fclose(fin);
fclose(fout);
return 0;
}