Cod sursa(job #1091991)

Utilizator heracleRadu Muntean heracle Data 26 ianuarie 2014 14:12:31
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <cstdio>

int sp[2001];
long long bst[2001];

int main()
{
    freopen("gaz.in","r",stdin);
    freopen("gaz.out","w",stdout);

    int l,p,d,c,n;
    scanf("%d%d%d%d",&l,&p,&d,&c);

    scanf("%d",&n);
    int x;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&x);
        sp[i]=sp[i-1]+x;
    }

    long long min,cost=-l,im;

    for(int i=1; i<=n; i++)
    {
        min=1999999999999;
        cost=0;
        for(int j=i-1; j>=0; j--)
        {
            if(bst[j]+cost*c+p+(sp[i]- sp[j])*d<min)
            {
                min=bst[j]+cost*c+p+(sp[i]- sp[j])*d;
                im=j;
            }
            if(sp[i]-sp[j]>l)
                cost+=sp[i]-sp[j]-l;



        }
        bst[i]=min;
    }
    printf("%lld",bst[n]);

    return 0;
}