Cod sursa(job #2912715)

Utilizator Vlad_NistorNIstor Vlad Vlad_Nistor Data 10 iulie 2022 11:23:26
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <bits/stdc++.h>

using namespace std;



#define dist first

#define lana second



pair<int,int> a[100004];

int heap[100004], h = 0;

void removeheap(){

    heap[1] = heap[h];

    h--;

    int t = 1, c =2;

    while(c <= h){

        if(c + 1 <= h && heap[c+1] > heap[c]){

            c++;

        }

        if(heap[c] < heap[t]){

            break;

        }

        swap(heap[t],heap[c]);

        t = c;

        c = t * 2;

    }

}



void addheap(int val){

    heap[++h] = val;

    int h1 = h;

    while(h1 > 1 && heap[h1 / 2] < heap[h1]){

        swap(heap[h1 / 2],heap[h1]);

        h1 /= 2;

    }

}

bool cmp(pair<int,int> a, pair<int,int> b){

    if(a.dist == b.dist){

        return (a.lana < b.lana);

    }else{

        return (a.dist < b.dist);

    }

}

int main(void){

    ofstream cout("lupu.out");

    ifstream cin("lupu.in");

    int n,l,x,adal = 0,kn = 0,c,d,maxim = -1;

    long long int ans = 0;

    cin >> n >> x >> l;

    for(int i = 1;i<=n;i++){

        cin >> c >> d;

        if(c <= x){

            a[++kn].dist = (x - c) / l + 1;

            a[kn].lana = d;

            maxim = max(maxim, a[kn].dist);

        }

    }

    sort(a+1,a+kn+1, cmp);

   // cout << endl << maxim <<

    int poz = kn;

    for(int i = maxim;i>=1;i--){

        while(a[poz].dist == i && poz > 0){

            addheap(a[poz].lana);

            poz--;

        }

        if(h){

            ans += heap[1];

            removeheap();

        }

    }

    cout << ans;

}