Pagini recente » Cod sursa (job #1756941) | Cod sursa (job #1611674) | Cod sursa (job #2853322) | Cod sursa (job #471675) | Cod sursa (job #2554535)
#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], used[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;
timp = 0;
added = 0;
for(i=0; i<n; i++){
if(oi[i].dist <= timp){
added++;
grupa[i] = gr;
adauga(i);
}
else{
timp += l;
if(added > 0)
gr++;
added = 0;
i--;
}
}
for(i=0; i<n; i++)
grupa[i] = gr - grupa[i] + 1;
lana = 0;
for(i=0; i<=gr; i++){
while(used[grupa[h[1]]] + i > grupa[h[1]])
sterge(1);
lana = lana + 1LL*oi[h[1]].lana;
used[grupa[h[1]]]++;
sterge(1);
}
fout << lana;
return 0;
}