Cod sursa(job #900630)

Utilizator Catah15Catalin Haidau Catah15 Data 28 februarie 2013 20:56:08
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define maxN 100010
#define int64 long long

int N, X, L;
int A[maxN], D[maxN];
int H[maxN], dim;
int64 sol;


void push (int nod)
{
    if (nod == 1) return;
    if (A[H[nod]] < A[H[nod / 2]]) return;
    if (A[H[nod]] == A[H[nod / 2]] && D[H[nod]] <= D[H[nod / 2]]) return;

    swap (H[nod], H[nod / 2]);

    push (nod / 2);
}


void pop (int nod)
{
    int nodmax = nod;
    int f1 = nod * 2, f2 = nod * 2 + 1;

    if (f1 <= dim && (A[H[f1]] > A[H[nodmax]] || (A[H[f1]] == A[H[nodmax]] && D[H[f1]] > D[H[nodmax]]))) nodmax = f1;
    if (f2 <= dim && (A[H[f2]] > A[H[nodmax]] || (A[H[f2]] == A[H[nodmax]] && D[H[f2]] > D[H[nodmax]]))) nodmax = f2;

    if (nodmax == nod) return;

    swap (H[nod], H[nodmax]);

    pop (nodmax);
}


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

    scanf ("%d %d %d", &N, &X, &L);

    for (int i = 1; i <= N; ++ i)
    {
        scanf ("%d %d", &D[i], &A[i]);

        H[++ dim] = i;
        push (dim);
    }

    while (dim)
    {
        int Q = H[1];

        swap (H[1], H[dim]);
        -- dim;
        pop (1);

        if (D[Q] > X) continue;

        sol += A[Q];

        for (int i = 1; i <= N; ++ i) D[i] += L;
    }

    printf ("%lld", sol);

    return 0;
}