Cod sursa(job #1003190)

Utilizator smaraldaSmaranda Dinu smaralda Data 29 septembrie 2013 21:40:21
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<stdio.h>
#include<set>
#include<algorithm>
#include<vector>
using namespace std;

struct OAIE {
    int lana,pasi;
    };

OAIE make (int a, int b) {
    OAIE ret = {a,b};
    return ret;
}

bool cmp (OAIE a, OAIE b) {
    return a.pasi > b.pasi;
}

multiset <int, greater <int> > sol;
vector <OAIE> v;

int x,l;

int main() {
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    int j,i,a,b,n,timp;
    long long res = 0;
    scanf("%d%d%d",&n,&x,&l);
    for(i = 1; i <= n; i++) {
        scanf("%d%d",&a,&b);
        if((x - a) / l >= 0)
            v.push_back(make(b,(x - a) / l));
        }

    v.push_back(make(0,-1));
    n = v.size();
    sort(v.begin(),v.end(),cmp);

    i = 0;
    timp = v[0].pasi;
    while(timp >= 0) {
        for(; i < n && v[i].pasi == timp; i++)
            sol.insert(v[i].lana);

        for(j = 1; !sol.empty() && j <= timp - v[i].pasi; j++) {
            res += *sol.begin();
            sol.erase(sol.begin());
            }
        timp = v[i].pasi;
        }
    printf("%lld\n",res);
    return 0;
}