Cod sursa(job #1292192)

Utilizator RaduStefanFMI - Radu Stefan RaduStefan Data 13 decembrie 2014 20:51:24
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<fstream>
#include<set>
using namespace std;
void quickSort(int v[],int w[], int left, int right) 
{
	int i = left, j = right;
	int tmp;
	int pivot = v[(left+right)/2];
	while (i < j)
	{
		while (v[i] < pivot)
			i++;
		while (v[j] > pivot)
			j--;
		if (i <= j) 
		{
			tmp = w[i];
			w[i] = w[j];
			w[j] = tmp;
			tmp=v[i];
			v[i]=v[j];
			v[j]=tmp;
			i++;
			j--;
		}
	}
	if (left < j)
		quickSort(v,w, left, j);
	if (i < right)
		quickSort(v,w, i, right);
}
int main()
{
	ifstream fcin("lupu.in");
	ofstream fcout("lupu.out");
	
	multiset <int> min;
	 
	int v[100001],w[100001],i,n,x,l,j,ok,s=0;
	fcin>>n>>x>>l;
	for(i=1;i<=n;i++)
	{
		fcin>>v[i]>>w[i];
		v[i]+=x;
	}
	quickSort(v,w,1,n);
	i=1;j=-l;
	while(i<=n)
	{
		j+=l;ok=1;
		if(j>x)break;
		while(ok)
		{
			ok=0;
			if(x+j>=v[i] && i<=n)
			{
				min.insert(w[i]*-1);
				ok=1;
				i++;
			}
		}
		multiset <int> :: iterator it = min.begin();
		if(*it!=0)
		{
			s-=	*it;
			min.erase(it);
		}
	}
	fcout<<s;
	return 0;
}