Cod sursa(job #347042)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 10 septembrie 2009 19:12:55
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

#define FIN "lupu.in"
#define FOUT "lupu.out"

#define N 100005

int n, x, l;

long long r;

pair <int, int> v[N];

priority_queue < int, vector <int> > q;

void read()
{
    int i;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d%d%d", &n, &x, &l);

    for (i = 1; i <= n; ++ i)
        scanf("%d %d", &v[i].first, &v[i].second);

}

int main()
{
    int i, j, k;

    read();

    sort(v + 1, v + n + 1);

    k = (x - v[1].first) / l;

    if (v[1].first + l * k <= x)
        ++ k;

    for (i = k, j = 1; i >= 1; -- i)
    {
        while (v[j].first + l * (i - 1) <= x && j <= n)
            q.push(v[j ++].second);

        if (!q.empty())
        {
            r += q.top();

            q.pop();
        }
    }

    printf("%lld\n", r);
}