Cod sursa(job #1417986)

Utilizator tatianazTatiana Zapirtan tatianaz Data 11 aprilie 2015 17:47:29
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;

ifstream is("lupu.in");
ofstream os("lupu.out");

long long N, X, L;
long long x, y;
long long sol, lvl;
long long mxm = -1;

struct oaie{
    long long dis, lana;
};

oaie o[100001];

priority_queue <long long> Q;

bool CMP(const oaie &a1, const oaie &a2)
{
    if ( a1.dis != a2.dis )
        return a1.dis > a2.dis;
    else
        return a1.lana > a2.lana;
}

int main()
{
    is >> N >> X >> L;
    for (int i = 1; i <= N; ++i)
    {
        is >> x >> y;

        o[++lvl].dis = (X-x)/L;
        o[lvl].lana = y;
        mxm = max(mxm, o[lvl].dis);

    }

    sort(o+1, o+lvl+1, CMP);

    int j = 1;
    for (int i = mxm; i >= 0; --i)
    {
        while (o[j].dis == i)
        {
            Q.push(o[j].lana);
            j++;
        }

        if (!Q.empty())
        {
            sol += Q.top();
            Q.pop();
        }

    }

    os << sol;

    is.close();
    os.close();
    return 0;
}