Cod sursa(job #837683)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 18 decembrie 2012 14:33:10
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <cstdio>
#include <algorithm>
#define MAX_SIZE 100001
#define left_son i << 1
#define right_son (i << 1) + 1
using namespace std;

typedef struct
{
    int t;
    int l;
}oaie;

bool cmp(oaie a ,oaie b)
{
    return  a.t < b.t;
}

oaie vect[MAX_SIZE];
int heap[MAX_SIZE];
int nh;
int N, X , L;
long long answer = 0;


void up_heap(int i)
{
    if ( i <= 1 ) return;
    if ( heap[i] > heap[ i >> 1] )
    {
        swap( heap[i] , heap[i >> 1]);
        up_heap(i >> 1);
    }
}

void down_heap(int i)
{
    int m = i;
    if ( left_son <= nh && heap[left_son] > heap[m]) m = left_son;
    if ( right_son <= nh && heap[right_son] > heap[m]) m = right_son;
    if (m != i)
    {
        swap( heap[i] , heap[m]);
        down_heap(m);
    }
}


int main()
{
    ifstream input("lupu.in");
    ofstream output("lupu.out");
    input >> N >> X >> L;

    for (int i =1;i<=N;i++)
    {
        int d , a;
        input >> d >> a;
        vect[i].t = (X- d) / L + 1;
        vect[i].l = a;
    }
    sort(vect+1 ,vect+N+1, cmp);
    int tmax = vect[N].t;
    int last = N;
    nh = 0;
    for (int i = tmax;i>0;i--)
    {
        while ( last > 0 && vect[last].t == i)
        {
            nh ++;
            heap[nh] = vect[last].l;
            up_heap(nh);
            last --;
        }
        if (nh != 0)
        {
            answer += heap[1];
            swap(heap[1],heap[nh--]);
            down_heap(1);
        }

    }
    output << answer;



    return 0;
}