Pagini recente » Cod sursa (job #2612925) | Cod sursa (job #586533) | Diferente pentru info-oltenia-2018/individual intre reviziile 16 si 11 | Cod sursa (job #3038928) | Cod sursa (job #300838)
Cod sursa(job #300838)
#include <cstdio>
long long n,s,t;
long long cost[100001];
long long dq[100001];
long long cos=0,nr;
long long st=1;
void stanga(long long i)
{
if(dq[st]+t<dq[i])
st++;
}
void dreapta(long long i)
{
while(nr && cost[dq[nr]] + (i-dq[nr]) * s >= cost[i] )//cat timp dq nu e vid si ultimul e mai scump decat i
--nr;
}
void citire()
{
long long a;
scanf("%lld%lld%lld",&n,&s,&t);
for(long long i=1;i<=n;i++)
{
scanf("%lld%lld",&cost[i],&a);
stanga(i);//scoate elem din stanga daca e prea indepartat (branza mai veche de t sapt)
dreapta(i);//scoate din dreapta branza mai scumpa
dq[++nr]=i;
cos=cos+(long long)(cost[dq[st]]+(i-dq[st])*s)*a;
}
}
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
citire();
printf("%lld\n",cos);
}