Cod sursa(job #1276337)

Utilizator nod_softwareBudisteanu Ionut Alexandru nod_software Data 26 noiembrie 2014 10:59:04
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 1.86 kb
#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 100002;

struct TWolf
{
    int iDistance, iGoal;
};

int n, x, l;
TWolf g_vArray[N];
priority_queue<int> heap;

//------------------------------------------------------------------------
bool comp(TWolf a, TWolf b)
{
    if (a.iDistance == b.iDistance)
        return a.iGoal > b.iGoal;

    return a.iDistance < b.iDistance;
}
//------------------------------------------------------------------------
void ReadData()
{
    freopen("lupu.in", "r", stdin);

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

    for (int i = 1; i <= n; ++i)
    {
        scanf("%d%d", &g_vArray[i].iDistance, &g_vArray[i].iGoal);

        if (g_vArray[i].iDistance > x)
        {
            --i;
            --n;
        }
    }
}
//------------------------------------------------------------------------
void Solve()
{
    long long lldGmax = 0, lldDistmax = (long long) x;

    while (lldDistmax - l >= g_vArray[1].iDistance)
        lldDistmax -= l;

    int i = 1;

    while (1)
    {
        if (g_vArray[i].iDistance > lldDistmax || i > n)
        {
            if (!heap.empty())
            {
                lldGmax += heap.top();
                heap.pop();
            }

            lldDistmax += l;

            if (lldDistmax > x)
                break;
        }

        if (g_vArray[i].iDistance <= lldDistmax && i <= n)
        {
            heap.push(g_vArray[i].iGoal);
            ++i;
        }
    }

    printf("%lld\n", lldGmax);
}
//------------------------------------------------------------------------
int main()
{
    freopen("lupu.out", "w", stdout);

    ReadData();

    sort(g_vArray+1, g_vArray+n+1, comp);

    Solve();

    return 0;
}
//------------------------------------------------------------------------