Cod sursa(job #1002666)

Utilizator smaraldaSmaranda Dinu smaralda Data 28 septembrie 2013 14:36:30
Problema Lupul Urias si Rau Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 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;
}

set <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,res = 0,a,b,n,timp;

    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 = res = 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("%d\n",res);
    return 0;
}