Cod sursa(job #209070)
| Utilizator | Data | 20 septembrie 2008 14:07:09 | |
|---|---|---|---|
| Problema | Branza | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.56 kb |
#include <stdio.h>
long long n, t, s, c[100010], p[100010], d[100010], o , r, to, k, i;
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%lld %lld %lld", &n, &s, &t);
k = 0;
r = 1;
for(i=1; i<=n; i++)
{
scanf("%d %d", &c[i], &p[i]);
if (d[r]<i-t) r++;
while((c[d[k]]+s*(i-d[k])>=c[i])&&(k>=r))
{
k--;
}
k++;
d[k] = i;
to += p[i]*(c[d[r]]+s*(i-d[r]));
}
printf("%lld\n", to);
return 0;
}
