Cod sursa(job #93087)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 17 octombrie 2007 17:41:23
Problema Branza Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <stdio.h>
#define NMAX 100100
#define MIN(a,b) (((a)<(b))?(a):(b))

int N, T, S, Poz[NMAX];
long long C[NMAX], P[NMAX], A[NMAX], B[NMAX], DQ[NMAX];

void read()
{
        int i;
        freopen("branza.in", "r", stdin);
        scanf("%d%d%d", &N, &S, &T);

        for (i = 0; i < N; i++)
            scanf("%d%d", P+i, C+i);
}

void solve()
{
        int i, lo, hi, c;

        DQ[0] = P[0]; A[0] = P[0]*C[0];

        for (lo = 0, hi = 1, i = 1; i < N; i++)
        {
                if (i-Poz[lo]>T) lo++;

                A[i] = A[i-1]+C[i]*MIN( (DQ[lo]+S*(i-Poz[lo])), P[i] );

                c = P[i];

                while ( (hi>lo)&&( (DQ[hi-1]+S*(i-Poz[hi-1]))>c ) ) hi--;
                DQ[hi] = c; Poz[hi++] = i;
        }
}

void brut()
{
        int i, j, x;
        
        B[0] = C[0]*P[0];

        for (i = 1; i < N; i++)
        {
                B[i] = B[i-1]+P[i]*C[i];
                x = i-T-1;
                if (x<0) x = 0;
                for (j = x; j < i; j++)
                    B[i] = MIN(B[i], B[i-1]+C[i]*(P[j]+S*(i-j)));
        }
}

void write()
{
        freopen("branza.out", "w", stdout);
        printf("%lld\n", A[N-1]);
        //freopen("brut.out", "w", stdout);
        //printf("%lld\n", B[N-1]);
}

int main()
{
        read();
        solve();
        //brut();
        write();
        return 0;
}