Cod sursa(job #2625594)

Utilizator bogdan.gusuleacGusuleac Bogdan bogdan.gusuleac Data 6 iunie 2020 01:17:49
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");

int main()
{
    long long int n, s, t, k;
    int v[100005];
    long long sum = 0;
    deque <long long int> d;

    fin >> n >> s >> t;

    for(int i = 1; i <= n; i++)
    {
        fin >> v[i] >> k;
        ///verificam t zile depasite
        if(!d.empty() && i - d.front() >  t)
            d.pop_front();

        ///verificam costul minim + taxa >= costul curent
        while(!d.empty() &&  (long long int)(v[d.back()] + (i-d.back()) * s ) >= v[i] )
            d.pop_back();
        d.push_back(i);

        sum += (long long int)(k * (v[d.front()] + (long long int)(i-d.front()) * s));

    }
    fout << sum;
    return 0;
}