Cod sursa(job #2790123)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 28 octombrie 2021 14:37:35
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

ifstream fin("branza.in");
ofstream fout("branza.out");

const int maxN = 100005;
int p[maxN], c[maxN], n, s, t, ans;
deque <int> dq;

int main()
{
    fin >> n >> s >> t;
    for(int i = 1; i <= n; i++)
        fin >> c[i] >> p[i];
    for(int i = 1; i <= n; i++)
    {
        while(!dq.empty() && (c[dq.back()] + (i - dq.back()) * s > c[i]))
            dq.pop_back();
        dq.push_back(i);
        if(dq.front() + t < i)
            dq.pop_front();
        ans += (c[dq.front()] + (i - dq.front()) * s) * p[i];
    }
    fout << ans;
    return 0;
}