Cod sursa(job #334945)
Utilizator | Data | 28 iulie 2009 12:17:58 | |
---|---|---|---|
Problema | Branza | Scor | 0 |
Compilator | cpp | Status | done |
Runda | splunge5 | Marime | 0.6 kb |
#include <stdio.h>
#define Nmax 100100
int n,s,t,inc=1,sf=0,cost;
struct coada{
int nr,poz;
};
coada q[Nmax];
int main()
{
int i,x,y;
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",&x,&y);
while(q[inc].poz <=i-t && inc<=sf)
++inc;
while(inc<=sf && ((i-q[sf].poz)*s+q[sf].nr)>x)
--sf;
q[++sf].poz=i;
q[sf].nr=x;
cost+=y*(q[inc].nr+s*(i-q[inc].poz));
}
printf("%d",cost);
}