Cod sursa(job #3142761)

Utilizator ecaterinaEcaterina Stefanescu ecaterina Data 24 iulie 2023 12:26:23
Problema Lupul Urias si Rau Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.43 kb
#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;
}