Cod sursa(job #1535195)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 24 noiembrie 2015 14:02:31
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstdio>
#include <queue>
#include <algorithm>

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

using namespace std;
int n, x, l, poz = 1, first, pos;
char buff[DIM];
LL sum;
struct oaie
{
    int dist;
    int w;
} v[NMAX];

bool cmp(const oaie &a, const oaie &b)
{
    return a.dist < b.dist;
}
priority_queue <int> pq;

void citire(int &nr)
{
    nr = 0;
    while(buff[pos] < '0' || buff[pos] > '9')
    {
        ++pos;
        if(pos == DIM)
        {
            pos = 0;
            fread(buff, 1, DIM, stdin);
        }
    }
    while(buff[pos] <= '9' && buff[pos] >= '0')
    {
        nr = nr*10 + buff[pos] - '0';
        ++pos;
        if(pos == DIM)
        {
            pos = 0;
            fread(buff, 1, DIM, stdin);
        }
    }
}

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);
    citire(n);
    citire(x);
    citire(l);
    for(int i = 1; i<= n; ++i) { citire(v[i].dist); citire(v[i].w); }
    sort(v+1, v+n+1, cmp);
    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;
}