Cod sursa(job #2912176)

Utilizator biancalautaruBianca Lautaru biancalautaru Data 7 iulie 2022 11:03:32
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda 17_iulie Marime 1.19 kb
#include <fstream>
#include <algorithm>
#define DIM 100001
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
int n,x,l,d,a,k,i,j,tmax,t,nr,h[DIM];
long long sol;
struct oaie {
    int t,l;
}v[DIM];

bool cmp(oaie a,oaie b) {
    if (a.t==b.t)
        return a.l>b.l;
    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) {
    while (2*k<=nr) {
        int p=2*k;
        if (p+1<=nr && h[p+1]>h[p])
            p++;
        if (h[p]>h[k]) {
            swap(h[p],h[k]);
            k=p;
        }
        else
            break;
    }
}

int main() {
    fin>>n>>x>>l;
    for (i=1;i<=n;i++) {
        fin>>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].l;
            upHeap(nr);
            j++;
        }
        if (nr!=0) {
            sol+=h[1];
            h[1]=h[nr--];
            downHeap(1);
        }
    }
    fout<<sol;
    return 0;
}