Cod sursa(job #2168873)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 14 martie 2018 12:38:14
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include<fstream>
using namespace std;
ifstream in ("lupu.in");
ofstream out ("lupu.out");
pair<int,int> heap[100001],v[100001];
long long sz,x,n,y,l,auxi,pas,sol;
bool comp (int x, int y) {
    if (heap[x].first == heap[y].first) {
        return heap[x].second > heap[y].second;
    }
    return heap[x].first > heap[y].first;
}
void up (int p) {
    while (p > 1 && comp (p,p/2)) {
        swap (heap[p],heap[p/2]);
        p /= 2;
    }
    return;
}
void down (int p) {
    while (p*2 <= sz) {
        int t = p*2;
        if (t < sz && comp (t+1,t)) {
            t++;
        }
        if (comp (t,p)) {
            swap (heap[t],heap[p]);
            p = t;
        }
        else {
            return;
        }
    }
    return;
}
void adauga (int x, int y) {
    sz ++;
    heap[sz].first = x;
    heap[sz].second = y;
    up (sz);
    return;
}
void sterge () {
    swap (heap[1],heap[sz]);
    sz --;
    down (1);
    return;
}
int main (void) {
    in >> n >> x >> l;
    for (int i = 1; i <= n; i ++) {
        in >> v[i].first >> v[i].second;
    }
    for (int i = 1; i <= n; i ++) {
        if (v[i].first == 0) {
            continue;
        }
        y = v[i].first;
        if (y > x) {
            v[i].first = -1;
        }
        else {
            auxi = y;
            if (auxi % l == 0) {
                v[i].first = auxi/l;
            }
            else {
                v[i].first = auxi/l + 1;
            }
        }
        if (v[i].first != -1) {
            adauga (v[i].first,v[i].second);
        }
    }
    if (x % l == 0) {
        x /= l;
    }
    else {
        x = x/l+1;
    }
    for (int i = 1; i <= n; i ++) {
        if (heap[1].first <= x) {
            sol += heap[1].second;
            x--;
            sterge ();
        }
        else {
            sterge ();
        }
    }
    out << sol;
    return 0;
}