Cod sursa(job #612912)

Utilizator CBogdanCiobanu Bogdan CBogdan Data 12 septembrie 2011 22:05:17
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include<cstdio>
#include<deque>
using namespace std;

long long N,S,T,C,P[100010],i,SOL;

deque<int> deq;

void read(),solve();

int main()
{
    read();
    solve();

    return 0;
}

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

    scanf("%lld%lld%lld",&N,&S,&T);
}

void solve()
{
    for(i=1;i<=N;i++)
    {
        scanf("%lld%lld",&P[i],&C);
        while(!deq.empty()&& P[deq.back()]+(i-deq.back())*S>P[i])deq.pop_back();
        deq.push_back(i);
        while(!deq.empty()&& deq.front()<=i-T)deq.pop_front();
        SOL+=P[deq.front()]*C+(i-deq.front())*S*C;
    }
    printf("%lld\n",SOL);
}