Cod sursa(job #67806)
Utilizator | Data | 25 iunie 2007 17:22:22 | |
---|---|---|---|
Problema | Branza | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 4.71 kb |
#include<stdio.h>
const long long maxn = 100001;
long long i;
long long st[maxn];
long long co[maxn];
long long can[maxn];
long long n;
long long din[maxn];
long long s;
long long t;
long long a[maxn];
long long b,l;
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%lld %lld %lld",&n,&s,&t);
for(i = 1;i <= n; ++i)
{
scanf("%lld %lld",&co[i],&can[i]);
}
b = 1;
for(i = 1;i <= n; ++i)
{
while(i - st[b] > t && b < l)
{
++b;
}
while(co[i] < co[st[l]] + (i - st[l]) * s && l >= b)
{
--l;
}
++l;
st[l] = i;
din[i] = din[i - 1] + can[i] * co[st[b]] + (long long)can[i] * s * (i - st[b]);
}
printf("%lld\n",din[n]);
return 0;
}