记录编号	43653	评测结果	AAAAAAAAAA
题目名称	[湖北2011寒假] 未名湖钓鱼	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2012-10-12 10:39:39	内存使用	2.99 MiB

#include <iostream>
#include <cstdio>
using namespace std;

int n,get[5010],die[5010];//heap

void swap(int& a,int& b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}

void checkget(int pos)//heap check (down)
{
	int maxget,maxpos,np;
	maxget=get[pos];
	maxpos=pos;
	np=pos*2;
	if (np<=n)
	{
		if (maxget<get[np])
		{
			maxget=get[np];
			maxpos=np;
		}
	}
	np=pos*2+1;
	if (np<=n)
	{
		if (maxget<get[np])
		{
			maxget=get[np];
			maxpos=np;
		}
	}
	if (maxpos!=pos)
	{
		swap(get[pos],get[maxpos]);
		swap(die[pos],die[maxpos]);
		checkget(maxpos);
	}
}

int main(void)
{
	freopen("fisha.in","r",stdin);
	freopen("fisha.out","w",stdout);
	int i,lim,walktim,fishtim;
	long long total=0;
	cin>>n>>lim>>walktim>>fishtim;
	for (i=1;i<=n;i++)
		cin>>get[i]>>die[i];
	lim-=walktim*(n-1);
	if (lim<=0)
	{
		cout<<'0'<<endl;
		return(0);
	}
	if (lim%fishtim==0)
		lim=lim/fishtim-1;
	else
		lim=lim/fishtim;
	for (i=(n>>1);i>=1;i--)
		checkget(i);
	while (lim)
	{
		if (get[1]<=0)
			break;
		lim--;
		total+=get[1];
		get[1]-=die[1];
		checkget(1);
	}
	cout<<total<<endl;
	return(0);
}