Cod sursa(job #2912666)

Utilizator Vlad_NistorNIstor Vlad Vlad_Nistor Data 9 iulie 2022 19:03:03
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda 17_iulie Marime 1.46 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+1;
    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);
    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;
}