Cod sursa(job #67694)

Utilizator DastasIonescu Vlad Dastas Data 25 iunie 2007 13:22:53
Problema Branza Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda Finala, Clasa a 10-a Marime 0.91 kb
#include <cstdio>
#define maxn 100000

FILE *in = fopen("branza.in","r"), *out = fopen("branza.out","w");

int n, s, t;
struct branza
{
    int c, p;
};

branza a[maxn];
int b[maxn];

void read()
{
    fscanf(in, "%d %d %d", &n, &s, &t);

    for ( int i = 0; i < n; ++i )
        fscanf(in, "%d %d", &a[i].c, &a[i].p);
}



int main()
{
    read();

    b[0] = a[0].p*a[0].c;

    int depozitate = 0;

    for ( int i = 1; i < n; ++i )
    {
        if ( i % t == 0 )
            depozitate = 0;

        if ( a[i].p*a[i].c+depozitate*s <= (a[i].p+a[i-1].p)*a[i].c+depozitate*s)
            b[i] = b[i-1] + a[i].p*a[i].c+depozitate*s;
        else
            depozitate += a[i].p, b[i] = b[i-1] + (a[i].p+a[i-1].p)*a[i].c+depozitate*s;
    }

    fprintf(out, "%d\n", b[n-1]);

	return 0;
}


/*
a:
12 1
21 2
27 4
45 5
52 3

b:
12*1
max(2*21+12, (2+1)*12+12+10*12) = 54

*/