Cod sursa(job #1554739)

Utilizator mirupetPetcan Miruna mirupet Data 21 decembrie 2015 17:51:57
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<cstdio>
#include<deque>
#define DIM 100005
using namespace std;

long long N, S, T, sol, X, Y, i;
long long v[DIM];
deque <long long> val;

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", &v[i], &Y);

                while (!val.empty() && v[val.back()] + S * (i - val.back()) > v[i])
                    val.pop_back();
                val.push_back(i);

                while (!val.empty() && i - val.front() > T)
                    val.pop_front();
                sol += (v[val.front()] + S * (i - val.front())) * Y;
            }

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