Pagini recente » Cod sursa (job #1461331) | Cod sursa (job #2023065) | Cod sursa (job #1151489) | Autentificare | Cod sursa (job #204891)
Cod sursa(job #204891)
#include<stdio.h>
int n,t,cate;
long long s,rez;
struct help
{
long long c;
int z;
};
help h[100005];
inline int father(int x)
{
return x>>1;
}
inline int left_son(int x)
{
return x<<1;
}
inline int right_son(int x)
{
return (x<<1)+1;
}
void upheap(int k)
{
help key=h[k];
while((k>1)&&(key.c<h[father(k)].c))
{
h[k]=h[father(k)];
k=father(k);
}
h[k]=key;
}
void swap(help &x,help &y)
{
help aux;
aux=x;
x=y;
y=aux;
}
void downheap(int k)
{
int son;
do
{
son=0;
if(left_son(k)<=cate)
{
son=left_son(k);
if(right_son(k)<=cate)
{
if(h[right_son(k)].c<h[son].c)
son=right_son(k);
}
if(h[son].c>=h[k].c)
son=0;
}
if(son)
{
swap(h[son],h[k]);
k=son;
}
}while(son);
}
void update()
{
int i;
for(i=1; i<cate; i++)
{
h[i].c+=s;
h[i].z++;
if(h[i].z==t)
{
h[i]=h[cate];
cate--;
downheap(i);
}
}
}
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d%lld%d",&n,&s,&t);
long long c,p;
for(cate=1; n; n--,cate++)
{
scanf("%lld%lld",&c,&p);
update();
h[cate].c=c;
upheap(cate);
rez+=h[1].c*p;
}
printf("%lld\n",rez);
return 0;
}