Pagini recente » Cod sursa (job #2660249) | Cod sursa (job #363909) | Istoria paginii runda/trasharena_bitch | Cod sursa (job #1966617) | Cod sursa (job #1609795)
#include <cstdio>
#include <algorithm>
#define MAXN 100000
int s[MAXN], e[MAXN], u[MAXN], heap[MAXN], k;
bool cmp(const int x, const int y){
return u[x]>u[y];
}
inline int tata(int p){
return (p-1)/2;
}
inline int fiust(int p){
return 2*p+1;
}
inline int fiudr(int p){
return 2*p+2;
}
inline void swap(int a, int b){
int aux=heap[a];
heap[a]=heap[b];
heap[b]=aux;
}
inline void coborare(int p){
int q, f=1;
while((f)&&(fiust(p)<k)){
q=fiust(p);
if((fiudr(p)<k)&&(heap[fiudr(p)]>heap[q])){
q=fiudr(p);
}
if(heap[q]>heap[p]){
swap(p, q);
p=q;
}else{
f=0;
}
}
}
inline void urcare(int p){
while((p>0)&&(heap[p]>heap[tata(p)])){
swap(p, tata(p));
p=tata(p);
}
}
int main(){
int n, x, l, i, j, a;
long long ans;
FILE *fin, *fout;
fin=fopen("lupu.in", "r");
fout=fopen("lupu.out", "w");
fscanf(fin, "%d%d%d", &n, &x, &l);
for(i=0; i<n; i++){
fscanf(fin, "%d%d", &a, &s[i]);
e[i]=i;
if(x-a<0){
u[i]=0;
}else{
u[i]=(x-a)/l+1;
}
}
std::sort(e, e+n, cmp);
i=0;
ans=0;
k=0;
x=u[0];
while((i<n)&&(u[e[i]]!=0)){
j=i;
while((x>u[e[i]])&&(k>0)){
ans+=heap[0];
k--;
heap[0]=heap[k];
coborare(0);
x--;
}
while((i<n)&&(u[e[i]]==u[e[j]])){
heap[k++]=s[e[i]];
urcare(k-1);
i++;
}
ans+=heap[0];
k--;
heap[0]=heap[k];
coborare(0);
x=u[e[j]]-1;
}
while((x>0)&&(k>0)){
ans+=heap[0];
k--;
heap[0]=heap[k];
coborare(0);
x--;
}
fprintf(fout, "%lld\n", ans);
fclose(fin);
fclose(fout);
return 0;
}