Cod sursa(job #1141749)

Utilizator classiusCobuz Andrei classius Data 13 martie 2014 09:30:20
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
//#include <iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

ifstream cin("lupu.in");
ofstream cout("lupu.out");
#define nmax 100001
int i,n,l,x,sum,sectmax;
vector<int> v[100001];

struct cmp{
    bool operator()(const int x1,const int x2){
        return x2<x1;
    }
};

int main(){
    cin>>n>>x>>l;
    for(i=1;i<=n;i++){
        int a,lana;
        cin>>a>>lana;
        int sect=(x-a)/l+1;
        if(sect>0){
            v[sect].push_back(lana);
            sectmax=max(sect,sectmax);
        }
    }
    for(i=1;i<=sectmax;i++){
        if(v[i].empty()){
            v[i].push_back(0);
        }else{
            sort(v[i].begin(),v[i].end());
        }
    }

    priority_queue<int, vector<int>, cmp> pq;

    for(i=1;i<=sectmax;i++){
        pq.push(v[i][v[i].size()-1]);
        int q=2;
        while(q<=i && v[i].size()>=q && v[i][v[i].size()-q]>pq.top()){
            pq.pop();
            pq.push(v[i][v[i].size()-q]);
            q++;
        }
    }
    while(!pq.empty()){
        sum+=pq.top();
        pq.pop();
    }
    cout<<'\n'<<sum;

    return 0;
}