Cod sursa(job #1503606)

Utilizator mirupetPetcan Miruna mirupet Data 16 octombrie 2015 16:28:19
Problema Branza Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<cstdio>
#include<deque>
using namespace std;

long long sol, X, Y, N, S, T, i;

deque <long long> val;
deque <long long> pos;

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

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

        scanf("%lld%lld", &X, &Y);
        val.push_back(X);
        pos.push_back(1);
        sol = X * Y;

        for (i = 2; i <= N; i++)
            {
                scanf("%lld%lld", &X, &Y);
                while (!pos.empty() && (i - pos.front() > T))
                {
                    val.pop_front();
                    pos.pop_front();
                }

                while (!val.empty() && !pos.empty() && X <= (val.back() + (i - pos.front()) * S))
                {
                    val.pop_back();
                    pos.pop_back();
                }

                val.push_back(X);
                pos.push_back(i);

                sol += Y * (val.front() + (i - pos.front()) * S);
            }

        printf("%lld\n", sol);
    }