Cod sursa(job #1502347)

Utilizator mirupetPetcan Miruna mirupet Data 14 octombrie 2015 16:25:55
Problema Branza Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<cstdio>
#include<deque>
#define DIM 100001
using namespace std;

long long N, S, T, X, Y;
long long sol, 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);

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

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

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

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

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