Cod sursa(job #1618273)

Utilizator din99danyMatei Daniel din99dany Data 27 februarie 2016 19:15:35
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <cstdio>
using namespace std;

#define DIM 100005
int v[DIM], d[DIM];
int n, s, t;


int main()
{

    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);

    int i, j, p, st, dr;
    long long k = 0;

    scanf("%d%d%d",&n,&s,&t);
    st = 1;
    dr = 0;

    for( i = 1; i <= n; ++i ){
        scanf("%d%d",&v[i],&p);
        while( st <= dr && v[i] < v[d[dr]] + ( i - d[dr] ) * s ) dr--;
        dr++;
        d[dr] = i;
        while( st <= dr &&  i - d[st] > t ) st++;
        k = k + ( long long )( v[d[st]] + ( i - d[st] ) * s ) * p;
    }


    printf("%lld",k);


    return 0;
}