Cod sursa(job #2329114)

Utilizator bogdi1bogdan bancuta bogdi1 Data 26 ianuarie 2019 13:03:21
Problema Lupul Urias si Rau Scor 84
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
struct Cmp
{
    bool operator()(const int &a, const int &b)
    {
        return a>b;
    }
};
multiset<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;
    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++){
        if((x-v[i].dist)/l==nr)
            s.insert(v[i].val);
        else{
            while(nr!=(x-v[i].dist)/l && s.size()){
                sol+=*s.begin();
                s.erase(s.begin());
                nr--;
            }
            nr=(x-v[i].dist)/l;
            s.insert(v[i].val);
        }
    }
    if(i==n+1){
        while(nr>=0 && s.size()){
            sol+=*s.begin();
            s.erase(s.begin());
            nr--;
        }
    }
    printf("%lld", sol);
    return 0;
}