Cod sursa(job #2809989)

Utilizator LuciBBadea Lucian LuciB Data 28 noiembrie 2021 00:35:09
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 1e5;

struct oita {
    int dist, lana;
};

oita v[NMAX];

bool cmp(oita a, oita b) {
    return a.dist < b.dist;
}

priority_queue <int> maxHeap;

int main() {
    int n, x, l, i, poz;
    long long ans;
    FILE *fin, *fout;

    fin = fopen("lupu.in", "r");
    fscanf(fin, "%d%d%d", &n, &x, &l);
    for(i = 0; i < n; i++)
        fscanf(fin, "%d%d", &v[i].dist, &v[i].lana);
    fclose(fin);

    sort(v, v + n, cmp);

    poz = x / l;
    i = 0;
    ans = 0;
    for(poz = x / l; poz >= 0; poz--) {
        while(i < n && (x - v[i].dist) / l == poz) {
            maxHeap.push(v[i].lana);
            i++;
        }
        if(!maxHeap.empty()) {
            ans += maxHeap.top();
            maxHeap.pop();
        }
    }

    fout = fopen("lupu.out", "w");
    fprintf(fout, "%lld", ans);
    fclose(fout);

    return 0;
}