Cod sursa(job #1535034)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 24 noiembrie 2015 11:30:51
Problema Lupul Urias si Rau Scor 20
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 0.95 kb
#include <cstdio>
#include <queue>
#include <algorithm>

#define in "lupu.in"
#define out "lupu.out"
#define NMAX 200007
#define LL long long

using namespace std;
int n, x, l, poz = 1, first;
LL sum;
struct oaie
{
    int dist;
    int w;
    bool operator <(const oaie &aux) const
    {
        return (dist <= aux.dist);
    }
} v[NMAX];

priority_queue <int> pq;

inline void add_to_pq(const int &edge)
{
    while(v[poz].dist <= edge && poz <= n)
    {
        pq.push(v[poz].w);
        ++poz;
    }
}

int main()
{
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
    scanf("%d %d %d", &n, &x, &l);
    for(int i = 1; i<= n; ++i) scanf("%d %d", &v[i].dist, &v[i].w);
    sort(v+1, v+n+1);
    for(int lim = 0; lim<= x; lim+=l)
    {
        add_to_pq(lim);
        if(pq.empty()) continue;
        first = pq.top();
        pq.pop();
        sum += first;
    }
    printf("%lld\n", sum);
    return 0;
}