Cod sursa(job #719065)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 21 martie 2012 13:06:54
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <queue>
#include <algorithm>

#define MAX 100050

using namespace std;

struct oaie
{
    long long d, lana;
} v[MAX];
long long maxim, n, d, l, suma;
priority_queue<long long> s;

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

void citire()
{
    ifstream in("lupu.in");
    //scanf("%d %d %d", &n, &d, &l);
    in>>n>>d>>l;
    for(int i = 1; i <= n; i++)
        in>>v[i].d>>v[i].lana;
}

void prepare()
{
    for(int i = 1; i <= n; i++)
        maxim = max(maxim, (v[i].d = (d - v[i].d) / l));
    sort(v + 1, v + n + 1, cmp);
}

void solve()
{
    prepare();
    int j = 1;
    for(int i = maxim; i >= 0; --i)
    {
        while(j <= n && v[j].d == i)
            s.push(v[j++].lana);
        if(!s.empty())
        {
            suma += s.top();
            s.pop();
        }
    }
}

void afisare()
{
    ofstream out("lupu.out");
    out<<suma;
    out.close();
}

int main()
{
    citire();
    solve();
    afisare();
    return 0;
}