Cod sursa(job #1051505)

Utilizator BlueStrutAndrei Prahoveanu BlueStrut Data 10 decembrie 2013 10:02:41
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
long long i, n, m, k, s, x, y, mx;
multiset<long long> heap;
multiset<long long>::iterator it;
vector< pair<long long,long long> > v;
vector< pair<long long,long long> >::iterator p;
int main() {
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    scanf("%lld%lld%lld", &n, &m, &k); s=0;
    //n=nr de oi||m=distanta maxima teleport||k=distanta cu care se departeaza
    for (i=1; i<=n; i++) {
        scanf("%lld%lld", &x, &y);
        if (x<=m) {
            if (x>mx) mx=x;
            v.push_back(make_pair(x, y));
        }
    }
    sort(v.begin(), v.end());
    p=v.begin();
    for (i=1;i<=mx/k+1;i++) {
        for (;p!=v.end()&&(*p).first<=i;p++)
            heap.insert(p->second);
        if (!heap.empty()) {
            it=heap.end();
            it--;
            s+=*it;
            heap.erase(it);
        }
    }
    printf("%lld\n", s);
    return 0;
}