Cod sursa(job #2170873)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 15 martie 2018 10:10:40
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 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].second == heap[y].second) {
        return heap[x].first < heap[y].first;
    }
    return heap[x].second > heap[y].second;
}
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 > x) {
          continue;
       }
       int aux = x - v[i].first;
       v[i].first = aux / l + 1;
       adauga (v[i].first, v[i].second);
    }
    pas = 1;
    n = sz;
    for (int i = 1; i <= n; i ++) {
        if (heap[1].first >= pas) {
            sol += heap[1].second;
            pas ++;
            sterge ();
        }
        else {
            sterge ();
        }
    }
    out << sol;
    return 0;
}