Cod sursa(job #383403)

Utilizator drujbarultudorTudor Mihai Munteanu drujbarultudor Data 16 ianuarie 2010 14:55:03
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include<cstdio>
int n,s,t,st,dr,k;
int i,a[10000],b[10000],dq[100000];
long long sum;
inline void stanga(int i)
{
	
    if (dq[st]==i-t)
        st=st+1;
}
void dreapta (int i)
{
    while  (st<=dr && a[i]<=a[dq[dr]]+s*(i-dq[dr]))
        dr=dr-1;
    dq[++dr]=i;
}
int main ()
{
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	scanf("%d%d%d",&n,&s,&t);
	st=1;
	dr=0;
	for (i=1;i<=n;i++)
		scanf("%d%d",&a[i],&b[i]);
		for (i=1;i<=n;i++)
		{
			stanga(i);
			dreapta(i);
			sum=sum+(long long)b[i]*(a[dq[st]]+s*(i-dq[st]));
		}
		printf("%d",sum);
return 0;
}