Cod sursa(job #1809204)

Utilizator PaulCbnCiobanu Paul PaulCbn Data 18 noiembrie 2016 18:31:05
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>
#include <cstdio>
#include <deque>
#define NMAX 100005

using namespace std;

int N,S,T;
deque<long long> dq;
long long c[NMAX];
logn long p[NMAX];
long long rez=0;

void citire()
{
    scanf("%d%d%d",&N,&S,&T);
    for(int i=1;i<=N;i++)
        scanf("%d%d",&c[i],&p[i]);
}

bool comp(int j, int i)
{
    return (i-j)*S+c[j] < c[i];
}

void rezolvare()
{
    dq.push_back(1);
    rez=c[1]*p[1];
    for(int i=2;i<=N;i++)
    {
        while(!dq.empty() && comp(dq.back(),i)==0)
            dq.pop_back();
        dq.push_back(i);

        if(i-dq.front()+1>T)
            dq.pop_front();

        rez+=p[i]*((i-dq.front())*S+c[dq.front()]);
    }
}

int main()
{
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    citire();
    rezolvare();
    printf("%lld",rez);
    return 0;
}