Cod sursa(job #2555419)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 24 februarie 2020 00:17:23
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include <cstdio>
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;

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

const int N = 100000;
struct oaie{
    int timp, lana;
} oi[N];

priority_queue <int> pq;

bool cmp(oaie a, oaie b){
    if(a.timp < b.timp)
        return true;
    return false;
}

int main()
{
    int n,x,l,i,p,dist,time,T;
    long long lana;
    fin >> n >> x >> l;
    p = 0;
    T = 0;
    for(i=0; i<n; i++){
        fin >> dist >> lana;
        if(dist <= x){
            oi[p].timp = (x - dist)/l + 1;
            T = max(T, oi[p].timp);
            oi[p++].lana = lana;
        }
    }
    n = p;
    sort(oi, oi+n, cmp);
    i = n-1;
    lana = 0;
    for(time = T; time > 0 && i >=0; time--){
        while(i >= 0 && oi[i].timp == time){
            pq.push(oi[i].lana);
            i--;
        }
        if(!pq.empty()){
            lana = lana + pq.top();
            pq.pop();
        }
    }
    fout << lana << "\n";
    return 0;
}