Cod sursa(job #881165)

Utilizator Theorytheo .c Theory Data 17 februarie 2013 19:15:27
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;

ifstream fin("lupu.in");
ofstream fout("lupu.out");

const int Nmax = 100009;

int N; int X; int L;int Heap[Nmax]; int HeapSize;

struct Oaie{ int w; int time;} V[Nmax];

bool cmp(const Oaie A, const Oaie B){

    if(A.time == B.time)return A.w > B.w;
    return A.time > B.time;
}

void Read() {

    fin >>N >> X >> L;
    for(int i = 1; i <= N; ++i)
        fin >> V[i].time >> V[i].w;
    sort(V + 1, V + 1 + N, cmp);
}

void GoUp(int X){

    int Father = X/2;
    if(Heap[Father] >=  Heap[X] &&  X != 1 ){
        swap(Heap[Father], Heap[X]);
        GoUp(Father);
    }
}

void GoDown(int X){

    int Change = X, LeftSon = X * 2, RightSon = X * 2 + 1;

    if(LeftSon <= HeapSize && Heap[Change] > Heap[LeftSon]) Change = LeftSon;

    if(RightSon <= HeapSize && Heap[Change] > Heap[RightSon]) Change = RightSon;

    if(Change != X){

        swap(Heap[X], Heap[Change]);
        GoDown(Change);
    }
}

void Solve(){

    int  p = 0; long long Sum = 0;

    for(int i = 1; i <= N; ++i)
        if(V[i].time + p * L <= X){

            Heap[++HeapSize] = V[i].w; ++p;
            GoUp(HeapSize);
        }else{
            if(Heap[1] < V[i].w){

                Heap[++HeapSize] = V[i].w;
                swap(Heap[HeapSize--] , Heap[1]);
                GoDown(1);
            }
        }

    for(int i = 1; i <= HeapSize; ++i) Sum += Heap[i];

    fout << Sum ;
}

int main(){

    Read ();

    Solve ();
    return 0;
}