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