Pagini recente » Cod sursa (job #1986270) | Cod sursa (job #2983240) | Cod sursa (job #1313245) | Cod sursa (job #1928260) | Cod sursa (job #881165)
Cod sursa(job #881165)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
const int Nmax = 100009;
int N; int X; int L;int Heap[Nmax]; int HeapSize;
struct Oaie{ int w; int time;} V[Nmax];
bool cmp(const Oaie A, const Oaie B){
if(A.time == B.time)return A.w > B.w;
return A.time > B.time;
}
void Read() {
fin >>N >> X >> L;
for(int i = 1; i <= N; ++i)
fin >> V[i].time >> V[i].w;
sort(V + 1, V + 1 + N, cmp);
}
void GoUp(int X){
int Father = X/2;
if(Heap[Father] >= Heap[X] && X != 1 ){
swap(Heap[Father], Heap[X]);
GoUp(Father);
}
}
void GoDown(int X){
int Change = X, LeftSon = X * 2, RightSon = X * 2 + 1;
if(LeftSon <= HeapSize && Heap[Change] > Heap[LeftSon]) Change = LeftSon;
if(RightSon <= HeapSize && Heap[Change] > Heap[RightSon]) Change = RightSon;
if(Change != X){
swap(Heap[X], Heap[Change]);
GoDown(Change);
}
}
void Solve(){
int p = 0; long long Sum = 0;
for(int i = 1; i <= N; ++i)
if(V[i].time + p * L <= X){
Heap[++HeapSize] = V[i].w; ++p;
GoUp(HeapSize);
}else{
if(Heap[1] < V[i].w){
Heap[++HeapSize] = V[i].w;
swap(Heap[HeapSize--] , Heap[1]);
GoDown(1);
}
}
for(int i = 1; i <= HeapSize; ++i) Sum += Heap[i];
fout << Sum ;
}
int main(){
Read ();
Solve ();
return 0;
}