Cod sursa(job #1494258)

Utilizator demetriad-dagpagDavid Demetriad demetriad-dagpag Data 30 septembrie 2015 21:20:12
Problema Branza Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.61 kb
#include <stdio.h>
#include <stdlib.h>
#define C 100000
long long c[C+1],p[C+1],v[C+1];
int main()
{
    long long n,s,t,i,min,a,b;
    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",&c[i],&p[i]);
    min=c[1]*p[1];
    v[1]=1;
    a=1,b=1;
    for(i=2; i<=n; i++)
    {
        while(a<b && v[a]+t<i)
            a++;
        while(b>=a && (c[v[b]]+s*(i-v[b]))>=c[i])
            b--;
        v[++b]=i;
        min+=p[i]*(c[v[a]]+s*(i-v[a]));
    }
    printf("%lld\n",min);

    return 0;
}