Pagini recente » Cod sursa (job #2155600) | Cod sursa (job #1759369) | Cod sursa (job #2401923) | Cod sursa (job #2823841) | Cod sursa (job #1309403)
#include <fstream>
#include<algorithm>
using namespace std;
ifstream in("lupu.in");
ofstream out("lupu.out");
struct oi{ int t, c;} v[100001];
int n,l,maxd,nr;
long long heap[100001];
bool cmp(oi a, oi b){
return a.t<b.t;
}
void schimba (int x, int y){
int a=heap[x];
heap[x]=heap[y];
heap[y]=a;
}
void urcare(int i){
while(i>=2 && heap[i] < heap[i/2]){
schimba(i,i/2);
i/=2;
}
}
void coborare(int i){
int fs = 2*i, fd = 2*i + 1, bun = i;
if (fs <= nr && heap[fs] < heap[bun])
bun = fs;
if (fd <= nr && heap[fd] < heap[bun])
bun = fd;
if (bun != i) {
schimba(i, bun);
coborare(bun);
}
}
int main()
{
in>>n>>maxd>>l;
int i,x;
for(i=1;i<=n;i++){
in>>x>>v[i].c;
v[i].t=(maxd-x)/l;
}
sort(v,v+n+1,cmp);
heap[++nr]=v[1].c;
for(i=2;i<=n;i++){
if(nr<=v[i].t){
heap[++nr]=v[i].c;
urcare(nr);
//out<<v[i].t<<" "<<v[i].c<<"\n";
}
else{
if(v[i].c>heap[1]){
heap[1]=v[i].c;
coborare(1);
//out<<v[i].t<<" "<<v[i].c<<"\n";
}
}
}
long long s1=0;
for(i=1;i<=nr;i++){
s1+=heap[i];
//out<<heap[i]<<" ";
}
out<<s1;
return 0;
}