Cod sursa(job #1806664)

Utilizator gabor.vlad13lil pump gabor.vlad13 Data 15 noiembrie 2016 16:46:34
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <iostream>
#include <cstdio>
#include <deque>
#define NMAX 100005

using namespace std;

int n, s, t;
long long suma;
struct numere
{
    int first;
    int second;

}vec[NMAX];

deque<int> dq;

void read()
{
    scanf("%d %d %d\n", &n, &s, &t);
    int x, y;
    for (int i=1; i<=n; i++)
    {
        scanf("%d %d\n", &vec[i].first, &vec[i].second);
    }

}

void verifica(int ind)
{
    while(!dq.empty() && (vec[ind].first < vec[dq.back()].first + s * (ind - dq.back())))
            dq.pop_back();
}
void solve()
{

    dq.push_back(1);
    suma+=vec[1].first * vec[1].second;
    for (int i=2; i<=n; i++)
    {
        /*if (vec[dq.back()].first + s > vec[i].first)
        {
            verifica(i);
            dq.push_back(i);
        }
        else
            dq.push_back(i);*/

        verifica(i);
        dq.push_back(i);
        if (i - dq.front() > t)
            dq.pop_front();
        suma = suma + (vec[dq.front()].first + s * (i - dq.front())) * vec[i].second;

    }
}

int main()
{

    freopen("branza.in", "r", stdin);
    freopen("branza.out", "w", stdout);
    read();
    solve();
    printf("%lld", suma);
    return 0;
}