Cod sursa(job #1036938)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 19 noiembrie 2013 19:21:14
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

long long n, x, l;

struct oaie
{
	long long t, m;
};
oaie a[100001];
struct comp
{
	bool operator()(const oaie &a, const oaie &b)
	{
		if(a.m<=b.m)
			return 1;
		return 0;
	};
};
priority_queue<oaie, vector<oaie>, comp>codita;
bool comps(oaie a, oaie b)
{
	if(a.t>b.t || (a.t==b.t && a.m>=b.m))
		return 1;
	return 0;
}

int main()
{
    freopen("lupu.in", "r", stdin);
    freopen("lupu.out", "w", stdout);
    scanf("%lld%lld%lld", &n, &x, &l);
    long long s=0, tmax=-1, j=0;
    for(int i=0;i<n;i++)
	{
		scanf("%lld%lld", &a[i].t, &a[i].m);
		if(l!=0)
			a[i].t=(x-a[i].t)/l+1;if(a[i].t>tmax)tmax=a[i].t;
	}
	if(l==0)
		for(int i=0;i<n;i++)
			s+=a[i].m;
	else
	{
		sort(a, a+n, comps);
		for(int i=tmax;i>=1;i--)
		{
			while(a[j].t==i && j<n)
				codita.push(a[j++]);
			s+=codita.top().m;
			codita.pop();
		}
	}
	printf("%lld", s);
    return 0;
}