Cod sursa(job #1806638)

Utilizator calin1Serban Calin calin1 Data 15 noiembrie 2016 16:24:06
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include <cstdio>
#include <deque>
#include <algorithm>
#define N 100005

using namespace std;

int n, s, t;

long long suma;

struct zi
{
    long long cost, cantitate;

}vec[N];

deque <int> dq;

void compara(int poz)
{
    while(!dq.empty() && vec[dq.back()].cost + s * (poz - dq.back()) > vec[poz].cost)
    {
        dq.pop_back();
    }

    dq.push_back(poz);

    if(poz - dq.front() > t)
    {
        dq.pop_front();
    }

    suma += (vec[dq.front()].cost + s * (poz - dq.front())) * vec[poz].cantitate;
}

void citire()
{
    scanf("%d %d %d\n", &n, &s, &t);

    scanf("%lld %lld\n", &vec[1].cost, &vec[1].cantitate);

    dq.push_front(1);

    suma = (vec[1].cost * vec[1].cantitate);

    for(int i = 2 ; i <= n ; ++i)
    {
        scanf("%lld %lld\n", &vec[i].cost, &vec[i].cantitate);

        compara(i);
    }

    printf("%lld",suma);
}

int main()
{
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);

    citire();

    return 0;
}