Cod sursa(job #2036104)
| Utilizator | Data | 10 octombrie 2017 12:06:11 | |
|---|---|---|---|
| Problema | Branza | Scor | 100 |
| Compilator | c | Status | done |
| Runda | Arhiva de probleme | Marime | 0.6 kb |
#include <stdio.h>
#include <stdlib.h>
int c[100001],deq[100001];
int main()
{
int n,s,t,p,u,i,k;
long long rez;
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d%d%d",&n,&s,&t);
scanf("%d%d",&c[1],&k);
p=u=1;
deq[1]=1;
rez=(long long)c[1]*k;
for(i=2; i<=n; i++)
{
scanf("%d%d",&c[i],&k);
while(p<=u && deq[p]<i-t)
p++;
while(u>=p && c[i]<c[deq[u]]+(i-deq[u])*s)
u--;
deq[++u]=i;
rez+=(long long)(c[deq[p]]+(i-deq[p])*s)*(long long)k;
}
printf("%lld\n",rez);
return 0;
}
