Cod sursa(job #718557)

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

#define MAX 100050

using namespace std;

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

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

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

void afisare()
{
    printf("%d", suma);
}

int main()
{
    freopen("lupu.in", "r", stdin);
    freopen("lupu.out", "w", stdout);

    citire();
    solve();
    afisare();

    fclose(stdin);
    fclose(stdout);
    return 0;
}