Pagini recente » Cod sursa (job #3005255) | Cod sursa (job #2870666) | Cod sursa (job #3261982) | Cod sursa (job #361555) | Cod sursa (job #3142761)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define NMAX 100001
int pas[NMAX];
long long int c[NMAX];
long long int heap[NMAX];
int heapsize;
static inline int leftchild(int i) {
return 2*i+1;
}
static inline int rightchild(int i) {
return 2*i+2;
}
static inline int parent(int i) {
return (i-1)/2;
}
void qsortpas(int begin, int end) {
int b, e, pivot;
b = begin;
e = end;
pivot = pas[(e+b)/2];
while (pas[b]<pivot) {
b++;
}
while (pas[e]>pivot) {
e--;
}
while (b<e) {
swap(pas[b], pas[e]);
swap(c[b], c[e]);
do {
b++;
} while (pas[b]<pivot);
do {
e--;
} while (pas[e]>pivot);
}
if (begin < e) {
qsortpas(begin, e);
}
if (e+1 < end) {
qsortpas(e+1, end);
}
}
void uphead(int nod) {
int father;
if (nod>0) {
father = parent(nod);
if (heap[father]<heap[nod]) {
swap(heap[father], heap[nod]);
uphead(father);
}
}
}
void downheap(int nod) {
int maxi, st, dr;
maxi = nod;
st = leftchild(nod);
dr = rightchild(nod);
if (st<heapsize && heap[st]>heap[maxi]) {
maxi = st;
}
if (dr<heapsize && heap[dr]>heap[maxi]) {
maxi = dr;
}
if (maxi!=nod) {
swap(heap[maxi], heap[nod]);
downheap(maxi);
}
}
void add(long long int val) {
heap[heapsize] = val;
heapsize++;
uphead(heapsize-1);
}
void extractmax() {
heap[0] = heap[heapsize-1];
heapsize--;
downheap(0);
}
int main() {
FILE *fin, *fout;
fin = fopen("lupu.in", "r");
fout = fopen("lupu.out", "w");
int n, x, l, i, start, end, nr, j;
long long int sum;
fscanf(fin, "%d%d%d", &n, &x, &l);
for (i=0; i<n; i++) {
fscanf(fin, "%d%lld", &pas[i], &c[i]);
pas[i] = (pas[i]+l-1)/l;
}
qsortpas(0, n-1);
// for (i=0; i<n; i++) {
// fprintf(fout, "%d %d\n", pas[i], c[i]);
// }
sum = 0;
for (i=0; i<n; i++) {
start = i;
end = i+1;
while (end<n && pas[start]==pas[end]) {
end++;
}
i=end-1;
for (j=start; j<end; j++) {
add(c[j]);
}
sum+=(long long)heap[0];
extractmax();
}
fprintf(fout, "%lld", sum);
fclose(fin);
fclose(fout);
return 0;
}