Mai intai trebuie sa te autentifici.
Cod sursa(job #238076)
Utilizator | Data | 31 decembrie 2008 14:47:08 | |
---|---|---|---|
Problema | Branza | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.47 kb |
#include<stdio.h>
#define N 100010
struct branza
{
int c,p;
};
branza a[N];
int n,s,t,d[N],p=1,u;
int rez;
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",&a[i].c,&a[i].p);
while(p<=u && i-d[p]>t)
++p;
while(p<=u && s*(i-d[u])+a[d[u]].c>=a[i].c)
--u;
d[++u]=i;
rez+=(a[d[p]].c+s*(i-d[p]))*a[i].p;
}
printf("%d\n",rez);
return 0;
}