Cod sursa(job #996252)

Utilizator thewildnathNathan Wildenberg thewildnath Data 11 septembrie 2013 15:22:34
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include<stdio.h>
#include<deque>
using namespace std;

long long c[100002],p[100002];

deque <long long> d;

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