Cod sursa(job #2032879)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 5 octombrie 2017 20:22:28
Problema Lupul Urias si Rau Scor 84
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define DIM 100002
#define INF 9223372036854775807

using namespace std;

ifstream f("lupu.in");
ofstream g("lupu.out");

int n, x, l, cnt;

long long s, val, maxim;

struct oaie
{
    int lana;
    long long d;
}oi[DIM];

bool cmp(oaie a, oaie b)
{
    return a.d > b.d;
}

priority_queue <int, vector<int> > h;

int main()
{
    f>>n>>x>>l;

    for(int i = 1; i <= n; ++ i)
    {
        f>>oi[i].d>>oi[i].lana;
        if(oi[i].d > x)
        {
            oi[i].d = INF;
            continue;
        }
        if(l != 0)
        {
            oi[i].d = (x - oi[i].d) / l + 1;
        }
        if(oi[i].d > maxim)
            maxim = oi[i].d;
    }

    sort(oi + 1, oi + n + 1, cmp);

    cnt = 1;

    for(long long i = maxim; i >= 1; -- i)
    {
        while(oi[cnt].d == i)
        {
            h.push(oi[cnt].lana);
            ++ cnt;
        }
        if(!h.empty())
        {
            s += h.top();
            h.pop();
        }

    }

    g<<s;

    return 0;
}