Cod sursa(job #2393205)

Utilizator cezar.plescaCezar Plesca cezar.plesca Data 31 martie 2019 00:43:07
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

int N,X,L;

struct Cmp
{
    bool operator ()(const pair<int,int> &a, const pair<int,int> &b)
    {
		if(a.first == b.first)
			return a.second > b.second;
		return a.first > b.first;
    }
};

struct less_than_key
{
    inline bool operator() (const pair<int,int> &a, const pair<int,int> &b)
    {
		return a.first > b.first;
    }
};

vector<pair<int,int>> oite;
int maxTime;
long long int B;

void blana(){
	vector<pair<int,int>>::iterator begin,end;
	begin=oite.begin();
	end=oite.end();

	priority_queue<int> Q;
	for(int time=maxTime;time>=0;time--){
		while(begin!=end && (*begin).first==time){			
			Q.push((*begin).second);		
			begin++;
		}
		if(!Q.empty()){
			B+=Q.top();
			Q.pop();
		}
	}
}

int main(){
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	
	scanf("%d %d %d",&N,&X,&L);

	int d,v,t;
    for (int i = 0; i < N; i++) {
        scanf("%d %d",&d,&v);
		if(d<=X){
			t=(X-d)/L;
			if(t>maxTime)
				maxTime=t;
			oite.push_back(make_pair(t,v));
		}
	}

	sort(oite.begin(),oite.end(),less_than_key());
	blana();
	printf("%lld\n",B);

    return 0;
}