Cod sursa(job #1303230)

Utilizator ioalexno1Alexandru Bunget ioalexno1 Data 27 decembrie 2014 19:30:57
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 2.01 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAX_N = 1e5 + 10;
struct oaie{

    int dist, cant, timp;
}a[MAX_N];

int heap[MAX_N], lgheap;

bool cmp(oaie x, oaie y){

    if(x.timp >= y.timp){

        x.cant = x.cant + y.cant - (y.cant = x.cant);
        x.dist = x.dist + y.dist - (y.dist = x.dist);
        return 0;
    }
    return 1;
}

void addheap(int i){

    heap[++lgheap] = i;
    int fiu = lgheap, tata = fiu / 2;
    bool e = true;
    while(tata >= 1 && e){

        e = false;
        if(a[heap[fiu]].cant > a[heap[tata]].cant){

            heap[fiu] = heap[fiu] + heap[tata] - (heap[tata] = heap[fiu]);
            fiu = tata;
            tata = fiu / 2;
            e = true;
        }
    }
}

int extractmax(){

    int aux = a[heap[1]].cant;
    heap[1] = heap[lgheap];
    --lgheap;
    int tata = 1, fiu = 2;
    bool e = true;
    while(fiu <= lgheap && e){

        e = false;
        if(a[heap[fiu + 1]].cant > a[heap[fiu]].cant && fiu + 1 <= lgheap)
            ++fiu;
        if(a[heap[tata]].cant < a[heap[fiu]].cant){

            heap[fiu] = heap[fiu] + heap[tata] - (heap[tata] = heap[fiu]);
            tata = fiu;
            fiu = tata * 2;
            e = true;
        }
    }
    return aux;
}

int main()
{

    freopen("lupu.in", "r", stdin);

    int n, x, l;
    scanf("%d %d %d\n", &n, &x, &l);
    for(int i = 1; i <= n; ++i){
        scanf("%d %d", &a[i].dist, &a[i].cant);
        a[i].timp = (x - a[i].dist) / l + 1;
        if(a[i].dist > x)
            a[i].timp = 0;

    }
    fclose(stdin);

    sort(a + 1, a + n + 1, cmp);
       freopen("lupu.out", "w", stdout);
    long long sol = 0;
    for(int i = n; i >= 1; --i){

        addheap(i);
        if(a[i].timp != a[i - 1].timp && lgheap > 0)
            for(int j = 1; j <= a[i].timp - a[i - 1].timp && lgheap > 0; ++j)
                sol += extractmax();
    }


    printf("%lld", sol);
    fclose(stdout);

    return 0;
}