Pagini recente » Cod sursa (job #1508928) | Cod sursa (job #31014) | Cod sursa (job #981557) | Autentificare | Cod sursa (job #712009)
Cod sursa(job #712009)
#include <fstream>
#include <algorithm>
#define NMAx 100100
#define timp first
#define profit second
#define left(i) (2*i)
#define right(i) (2*i+1)
#define father(i) (i/2)
#define cmp(a,b) (V[Heap[a]].profit>V[Heap[b]].profit)
using namespace std;
pair <int,int> V[NMAx];
int N,X,L,Vf,Heap[NMAx];
long long Sol;
void Up(int nod) {
while(nod>1&&cmp(nod,father(nod))) {
swap(Heap[nod],Heap[father(nod)]);
nod=father(nod);
}
}
void Down(int nod) {
int son;
do {
son=0;
if(left(nod)<=Vf) {
son=left(nod);
if(right(nod)<=Vf&&cmp(right(nod),left(nod)))
son=right(nod);
if(cmp(nod,son))
son=0;
}
if(son) {
swap(Heap[nod],Heap[son]);
nod=son;
}
}while(son);
}
void citire() {
ifstream in("lupu.in");
in>>N>>X>>L;
for(int i=1;i<=N;i++) {
in>>V[i].timp>>V[i].profit;
V[i].timp=(X-V[i].timp)/L+1;
}
in.close();
}
int main() {
int i,k;
citire();
sort(V+1,V+N+1);
reverse(V+1,V+N+1);
for(k=V[1].timp,i=1;k>=1;k--) {
for(;V[i].timp>=k&&i<=N;i++) {
Heap[++Vf]=i;
Up(Vf);
}
Sol+=V[Heap[1]].profit;
Heap[1]=Heap[Vf--];
Down(1);
}
ofstream out("lupu.out");
out<<Sol<<'\n';
out.close();
return 0;
}