比赛 |
20121012上午 |
评测结果 |
AAAAAAAAAA |
题目名称 |
未名湖钓鱼 |
最终得分 |
100 |
用户昵称 |
Truth.Cirno |
运行时间 |
0.021 s |
代码语言 |
C++ |
内存使用 |
3.18 MiB |
提交时间 |
2012-10-12 10:39:11 |
显示代码纯文本
#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);
}