Cod sursa(job #333252)

Utilizator zbarniZajzon Barna zbarni Data 21 iulie 2009 21:51:20
Problema Lupul Urias si Rau Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define pb push_back
#define mp make_pair
#define nx 100005
#define inf 
using namespace std;
vector <pair <int,int> > a;
int n,x,l,heap[nx],L;
long long sol;
struct asd
{
	int tim,poz;
};
asd t[nx];
bool cmp (const asd &a,const asd &b)
{
	return a.tim>b.tim;
}
void upheap (int x)
{
	int aux;
	while (x/2 && a[heap[x]].second>a[heap[x/2]].second)
	{
		aux=heap[x];
		heap[x]=heap[x/2];
		heap[x/2]=aux;
	}
}
void downheap(int x)
{
	int y=0,aux;
	while (y!=x)
	{
		y=x;
		if (y*2<=L && a[heap[y*2]].second>a[heap[x]].second)
			x=y*2;
		if (y*2+1<=L && a[heap[y*2+1]].second>a[heap[x]].second)
			x=y*2+1;
		aux=heap[x];
		heap[x]=heap[y];
		heap[y]=aux;
	}
}
int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	scanf("%d%d%d",&n,&x,&l);
	int i,p,q,j;a.pb(mp(0,0));
	for (i=1;i<=n;++i)
	{
		scanf("%d%d",&p,&q);
		a.pb(mp(p,q));
		if (p>x) t[i].tim=-1;
		else t[i].tim=(x-p)/l;
		t[i].poz=i;		
	}
	sort(t+1,t+n+1,cmp);
	for (i=1;t[1].tim>=0;t[1].tim--)
	{
		if (t[i].tim>-1) {
		heap[++L]=t[i].poz;
		upheap(L); 
		for (j=i+1;j<=n && t[j].tim==t[i].tim;++j)
		{
			heap[++L]=t[j].poz;
			upheap(L);
		} i=j-1; i++;}
		if (L>0)
		{
			sol+=a[heap[1]].second;
			heap[1]=heap[L--];		
			downheap(1);
		}
	}
	printf("%lld\n",sol);
	return 0;
}