Cod sursa(job #3126400)

Utilizator dnprxDan Pracsiu dnprx Data 6 mai 2023 16:42:35
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin ("branza.in");
ofstream fout ("branza.out");
deque <int> dq;
int c[100003];
int main()
{
    int i, p, n, s, t;
    fin >> n >> s >> t;
    t++;
    long long sum = 0;
    for (i = 0; i < n; i++)
    {
        fin >> c [i] >> p;
        if (!dq.empty() && dq.front() == i - t)
            dq.pop_front();

        while (!dq.empty() && c [i] <= c [dq.back()] + s * (i - dq.back()))
            dq.pop_back();

        dq.push_back(i);
        sum += (long long)p * (c[dq.front()] + s * (i - dq.front()));
    }
    fout << sum << "\n";
    return 0;
}