Cod sursa(job #549639)

Utilizator unknownliviuMaria Liviu Valentin unknownliviu Data 8 martie 2011 20:30:26
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<queue>
#include<fstream>
using namespace std;
ifstream in("lupu.in");
ofstream out("lupu.out");
const int N=100010;

int n,q,r;

priority_queue<int,vector<int>, greater<int> > c;
pair<int,int> v[N];

void read()
{
	in>>n>>r>>q;
	int d,a;
	for(int i=1;i<=n;i++)
	{
		in>>v[i].first>>v[i].second;
		//in>>d>>a;
		//c.push(make_pair(a,d));
	}
}

void solve()
{
	sort(&v[1],&v[n+1]);
	long long s = 0, dist = 0;
	int i;
	for(i=n ; i>=1 ; i--)
		if(v[i].first <= r)
			break;
	for(; i>=1 ; i--)
	{
		if(v[i].first + dist <= r)
		{
			s += v[i].second;
			c.push(v[i].second);
			dist += q;
			continue;
		}
		if(v[i].second > c.top())
		{
			s += v[i].second - c.top();
			c.pop();
			c.push(v[i].second);
		}
	}
	out<<s<<"\n";
}

int main()
{
	read();
	solve();
	return 0;
}