Cod sursa(job #911937)

Utilizator assa98Andrei Stanciu assa98 Data 11 martie 2013 22:52:36
Problema Branza Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <cstdio>
#include <deque>
using namespace std;

deque<long long> d;

int n;

long long s,t;

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

long long sol;

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