Cod sursa(job #2329130)

Utilizator bogdi1bogdan bancuta bogdi1 Data 26 ianuarie 2019 13:14:44
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
struct Cmp
{
    bool operator()(const int &a, const int &b)
    {
        return a<b;
    }
};
priority_queue<int, vector<int>, Cmp> s;
struct Oi
{
    int dist,val;
} v[100005];
bool comp(Oi a, Oi b)
{
    return a.dist<b.dist;
}
int main()
{   freopen("lupu.in", "r",stdin);
    freopen("lupu.out", "w",stdout);
    int n,x,l,i,nr,aux;
    long long sol=0;
    scanf("%d%d%d", &n, &x, &l);
    for(i=1; i<=n; i++)
        scanf("%d%d", &v[i].dist, &v[i].val);
    sort(v+1, v+n+1, comp);
    nr=(x-v[1].dist)/l;
    for(i=1; i<=n && nr>=0; i++){
        aux=(x-v[i].dist)/l;
        if(aux==nr)
            s.push(v[i].val);
        else{
            while(nr!=aux && nr>=0 && !s.empty()){
                sol+=s.top();
                s.pop();
                nr--;
            }
            nr=aux;
            s.push(v[i].val);
        }
    }
    if(i==n+1){
        while(nr>=0 && !s.empty()){
            sol+=s.top();
            s.pop();
            nr--;
        }
    }
    printf("%lld", sol);
    return 0;
}