Cod sursa(job #209070)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad 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;
}