Cod sursa(job #1554723)

Utilizator mirupetPetcan Miruna mirupet Data 21 decembrie 2015 17:29:57
Problema Branza Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
//#include<cstdio>
#include<fstream>
#include<deque>
using namespace std;

ifstream f("branza.in");
ofstream g("branza.out");

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

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

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

        //scanf("%d%d%d", &N, &S, &T);*/

        f >> N >> S >> T;

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

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

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

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

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