Cod sursa(job #911913)

Utilizator assa98Andrei Stanciu assa98 Data 11 martie 2013 22:40:01
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <cstdio>
using namespace std;

long long d[100100];

long long s,t;

long long sol;

long long a[100100],b[100100];

int beg;
int end;

int main()
{
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    int n;
    scanf("%d%lld%lld",&n,&s,&t);
    beg=1;
    sol=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&a[i],&b[i]);
        while(beg<end&&i-d[beg]>t)
            beg++;
        while(beg<end&&a[d[beg]]+(i-d[beg])*s>a[i])
            end--;
        d[++end]=i;
        sol+=a[d[beg]]*b[i]+b[i]*(i-d[beg])*s;
    }
    printf("%lld",sol);
    return 0;
}