Cod sursa(job #3135443)

Utilizator DariusGhercaDarius Gherca DariusGherca Data 3 iunie 2023 12:00:07
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
const int N = 1e5 + 10;

int v[N];

int main()
{
    deque <int> m;
    long long n, s, t;
    ifstream f("branza.in");
    f >> n >> s >> t;
    long long sum = 0;
    for(long long i = 1;i <= n; i++){
        long long a, b;
        f >> a >> b;
        v[i] = a;
        while(!m.empty() && v[i] <= v[m.back()] + s * (i - m.back()))
            m.pop_back();
        m.push_back(i);
        while(!m.empty() && i - m.front() > t)
            m.pop_front();
        sum += b * (v[m.front()] + s * (i - m.front()));
    }
    ofstream g("branza.out");
    g << sum;
    return 0;
}