Cod sursa(job #1494256)

Utilizator demetriad-dagpagDavid Demetriad demetriad-dagpag Data 30 septembrie 2015 21:17:23
Problema Branza Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.59 kb
#include <stdio.h>
#include <stdlib.h>
#define C 100000
int c[C+1],p[C+1],v[C+1];
int main()
{
    int n,s,t,i,min,a,b;
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    scanf("%d%d%d",&n,&s,&t);
    for(i=1; i<=n; i++)
        scanf("%d%d",&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("%d\n",min);

    return 0;
}