Cod sursa(job #2807557)

Utilizator AswVwsACamburu Luca AswVwsA Data 23 noiembrie 2021 22:08:59
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <fstream>
#include <climits>
#include <deque>
#define ll long long
using namespace std;
deque <ll> d;
const int NMAX = 100003;
ll v[NMAX];

ifstream cin("branza.in");
ofstream cout("branza.out");
int main()
{
    ll n, s, t;
    ll ans = 0;
    cin >> n >> s >> t;
    for (int i = 1; i <= n; i++)
    {
        ll q;
        cin >> v[i] >> q;
        if (!d.empty() and d.front() == i - t)
            d.pop_front();
        while (!d.empty() and v[d.back()] + (i - d.back()) * s >= v[i])
            d.pop_back();
        d.push_back(i);
        ans += q * (v[d.front()] + (i - d.front()) * s);
    }
    cout << ans;
}