Cod sursa(job #2916513)

Utilizator carinamariaCarina Maria Viespescu carinamaria Data 30 iulie 2022 12:17:32
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("lupu.in");
ofstream cout("lupu.out");
int i, j, n, m, l, d, a, x, k, tmax, nr;
int h[1000005];
long long sol;

struct oaie {
    int t,cost;
}v[100005];

bool cmp(oaie a,oaie b) {
    if (a.t==b.t)
        return a.cost>b.cost;
    return a.t>b.t;
}

void upHeap(int k) {
    while (k>1 && h[k]>h[k/2]) {
        swap(h[k],h[k/2]);
        k/=2;
    }
}
void downHeap(int k){
    int p=k;
    int c=2*p;
    while (c<=nr){
        if (c+1<=nr && h[c+1]>h[c])
            c++;
        if (h[c]>h[p]) {
            swap(h[c],h[p]);
            p=c;
            c=2*p;
        }
        else
            break;
    }
}

int main() {
    cin>>n>>x>>l;
    for (i=1;i<=n;i++) {
        cin>>d>>a;
        if (d<=x){
            v[++k]={(x-d)/l+1,a};
            tmax=max(tmax,v[k].t);
        }
    }
    sort(v+1,v+k+1, cmp);
    j=1;
    for (i=tmax;i>=1;i--){
        while (j<=k && v[j].t==i){
            h[++nr]=v[j].cost;
            upHeap(nr);
            j++;
        }
        if (nr!=0) {
            sol+=h[1];
            h[1]=h[nr];
            nr--;
            downHeap(1);
        }
    }
    cout<<sol;
}