Cod sursa(job #2802963)

Utilizator lolismekAlex Jerpelea lolismek Data 19 noiembrie 2021 10:09:51
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("branza.in"); ofstream fout("branza.out");
const int N = 1e5 + 1;
long long v[N], qt[N];
deque <long long> deq;
int main()
{
    long long n, s, t, i, total;
    fin >> n >> s >> t;
    for(i = 0; i < n; i++) fin >> v[i] >> qt[i];
    total = 0;
    ///t++;
    for(i = 0; i < n; i++){
        if(!deq.empty() && deq.front() == i - t) deq.pop_front();
        while(!deq.empty() && s * (i - deq.back()) + v[deq.back()] >= v[i]) deq.pop_back();
        deq.push_back(i);
        total += qt[i] * (v[deq.front()] + s * (i - deq.front()));
    }
    fout << total;
    return 0;
}