Cod sursa(job #718573)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 20 martie 2012 21:35:07
Problema Lupul Urias si Rau Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <set>
#include <algorithm>

#define MAX 100050

using namespace std;

struct oaie
{
    long long d, lana;
} v[MAX];
long long maxim, n, d, l, suma;
set<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;
    set<long long>::iterator it;
    for(int i = maxim; i >= 0; --i)
    {
        while(j <= n && v[j].d == i)
            s.insert(v[j++].lana);
        if(!s.empty())
        {
            it = s.end();
            it--;
            suma += (long long)(*it);
            s.erase(it);
        }
    }
}

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

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