Pagini recente » Rating Ioana Agheorghiesei (ioana_agheorghiesei) | Cod sursa (job #2574205) | Cod sursa (job #1649777) | Rating Beatrice Elena Salavastru (beatrice.salavastru) | Cod sursa (job #2554531)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
const int N = 100000;
struct oaie{
int dist, lana;
} oi[N];
int h[N+1], grupa[N+1];
int nh;
void schimba(int p, int q){
swap(h[p], h[q]);
}
bool compare(int p, int q){
if(oi[h[p]].lana > oi[h[q]].lana)
return true;
else if(oi[h[p]].lana == oi[h[q]].lana && grupa[h[p]] > grupa[h[q]])
return true;
return false;
}
void urca(int p){
while(p>1 && compare(p, p/2)){
schimba(p, p/2);
p /= 2;
}
}
void coboara(int p){
int fs = 2*p;
int fd = 2*p+1;
int bun = p;
if(fs <= nh && compare(fs, bun))
bun = fs;
if(fd <= nh && compare(fd, bun))
bun = fd;
if(bun != p){
schimba(p, bun);
coboara(bun);
}
}
void adauga(int x){
h[++nh] = x;
urca(nh);
}
void sterge(int p){
schimba(p, nh--);
urca(p);
coboara(p);
}
bool cmp(oaie a, oaie b){
if(a.dist < b.dist)
return true;
return false;
}
int main()
{
int n,x,l,i,gr,timp,added;
long long lana;
fin >> n >> x >> l;
for(i=0; i<n; i++)
fin >> oi[i].dist >> oi[i].lana;
sort(oi, oi+n, cmp);
while(n>=0 && oi[n-1].dist > x)
n--;
gr = 0;
for(i=0; i<n; i++){
grupa[i] = (x - oi[i].dist) / l;
gr = max(gr, grupa[i]);
adauga(i);
}
lana = 0;
for(i=0; i<=gr; i++){
while(grupa[h[1]] < i)
sterge(1);
lana = lana + 1LL*oi[h[1]].lana;
sterge(1);
}
fout << lana;
return 0;
}