Cod sursa(job #354870)
Utilizator | Data | 9 octombrie 2009 19:18:45 | |
---|---|---|---|
Problema | Branza | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.45 kb |
#include<stdio.h>
int N,T,S,v[100010],v1[100010],dq[100010],st,dr,Suma;
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d %d %d",&N,&S,&T);
for(int i=1;i<=N;++i)
scanf("%d %d",&v[i],&v1[i]);
st=1;
dr=0;
for(int i=1;i<=N;++i)
{
while(st<=dr&&v[i]<v[dq[dr]]+S*(i-dq[dr]))
--dr;
dq[++dr]=i;
if(st+1==i-T-1)
++st;
Suma=Suma+(v[dq[st]]+(i-dq[st])*S)*v1[i];
printf("%d %d\n",Suma,dq[st]);
}
}