Cod sursa(job #3196554)

Utilizator emazareMazare Emanuel emazare Data 24 ianuarie 2024 11:16:20
Problema Lupul Urias si Rau Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

ifstream fin("lupu.in");
ofstream fout("lupu.out");

const int Nmax = 100005;
struct oica{
    int d;
    int val;
    int step;
} v[Nmax];
priority_queue<int> q;

bool cmp(oica a, oica b){
    return(a.d<b.d);
}

int main()
{
    int n,x,l,i,j,cnt = 0;
    fin >> n >> x >> l;
    for(i=1;i<=n;i++)
        fin >> v[i].d >> v[i].val;
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++){
        if(x<v[i].d)
            v[i].step = 0;
        else
            v[i].step = min(n,(x-v[i].d)/l+1);
        v[i].step = n+1-v[i].step;
    }
    j = 0;
    for(i=1;i<=n;i++){
        while(j<n && v[j+1].step<=i){
            j++;
            q.push(v[j].val);
        }
        if(!q.empty()){
            cnt+=q.top();
            q.pop();
        }
    }
    fout << cnt;
    return 0;
}