Cod sursa(job #3143509)

Utilizator ecaterinaEcaterina Stefanescu ecaterina Data 30 iulie 2023 22:10:10
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.47 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, maxi, p;
    long long int sum;
    
    fscanf(fin, "%d%d%d", &n, &x, &l);
    maxi=0;
    for (i=0; i<n; i++) {
        fscanf(fin, "%d%lld", &pas[i], &c[i]);
        pas[i] = (x-pas[i]+l)/l;
        if (pas[i]>maxi) {
            maxi = pas[i];
        }
    }
    
    qsortpas(0, n-1);
    
//    for (i=0; i<n; i++) {
//        fprintf(fout, "%d %d\n", pas[i], c[i]);
//    }
    
    sum = 0;
    
    
    i=n-1;
    for (p=maxi; p>0; p--) {
        while (i>=0 && pas[i]>=p) {
            add(c[i]);
            i--;
        }
        if (heapsize>0) {
            sum+=(long long)heap[0];
            extractmax();
        }
    }
    
    fprintf(fout, "%lld", sum);
    
    
    fclose(fin);
    fclose(fout);
    return 0;
}