Cod sursa(job #209428)
| Utilizator | Data | 22 septembrie 2008 13:41:41 | |
|---|---|---|---|
| Problema | Branza | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.49 kb |
#include <stdio.h>
int n,s,t,i,j,c[100010],p[100010],d[100010],a[100010],st,fi,sol;
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d%d%d",&n,&s,&t);
for (i=1; i<=n; ++i) scanf("%d%d",&c[i],&p[i]);
d[1]=c[1];
a[1]=1;
st=1; fi=1;
sol=c[1]*p[1];
for (i=2; i<=n; ++i)
{
while (c[i]<c[a[fi]]+(i-a[fi])*s && fi>=st) --fi;
a[++fi]=i;
if (t<i-a[st]) ++st;
sol+=(c[a[st]]+(i-a[st])*s)*p[i];
}
printf("%d\n",sol);
return 0;
}