Pagini recente » Cod sursa (job #1259885) | Cod sursa (job #1680981) | Cod sursa (job #2841557) | Cod sursa (job #1566994) | Cod sursa (job #998568)
Cod sursa(job #998568)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
int N,X,L;
struct Sheep{
int time;
int value;
};
Sheep Array[100002];
int Dist[100002];
int Poz[100002];
int Heap[100002],Result,NHeap;
bool compare(Sheep a,Sheep b)
{
return a.time>b.time;
}
void Swap(int X, int Y)
{
swap(Heap[X],Heap[Y]);
swap(Poz[Heap[X]],Poz[Heap[Y]]);
}
void Read()
{
int i;
f>>N>>X>>L;
for(i=1;i<=N;i++)
{
f>>Dist[i]>>Array[i].value;
Array[i].time=(X-Dist[i])/L;
}
sort(Array+1,Array+N+1,compare);
}
void Percolate (int X)
{
int Father=(X>>1);
if (Father>0 && Array[Heap[X]].value>Array[Heap[Father]].value)
{
Swap (X,Father);
Percolate (Father);
}
}
void Sift(int X)
{
int Son=(X<<1);
if(Son+1<=NHeap && Array[Heap[Son+1]].value>Array[Heap[Son]].value)
Son++;
if(Son<=NHeap && Array[Heap[Son]].value>Array[Heap[X]].value)
{
Swap(Son,X);
Sift(Son);
}
}
void Insert(int X)
{
Heap[++NHeap]=X;
Poz[X]=NHeap;
Percolate(NHeap);
}
void Erase(int K)
{
Swap(K,NHeap);
--NHeap;
Sift(K);
}
void Solve()
{
int i;
int value=Array[1].time;
for(i=1;i<=N;i++)
{
if(Array[i].time!=value)
{
value=Array[i].time;
if(NHeap) Result+=Array[Heap[1]].value;
Erase(1);
}
Insert(i);
}
if (NHeap) Result+=Array[Heap[1]].value;
}
int main()
{
Read();
Solve();
g<<Result<<"\n";
return 0;
}