Cod sursa(job #2879624)

Utilizator MihneaStoicaMihnea Teodor Stoica MihneaStoica Data 28 martie 2022 19:49:26
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream cin ("branza.in");
ofstream cout ("branza.out");

long long c[100001], p[100001];

int main()
{
    int n, s, t;
    cin >> n >> s >> t;
    for (int i = 1; i <= n; i ++)
    {
        cin >> c[i] >> p[i];
    }
    
    long long ans = 0;
    deque<int> d;
    for (int i = 1; i <= n; i ++)
    {
        while (!d.empty() && c[i] <= c[d.back()] + s * (i - d.back()))
            d.pop_back();
        d.push_back(i);
        while (!d.empty() && d.front() < i - t)
            d.pop_front();
        ans += p[i] * (c[d.front()] + s * (i - d.front()));
    }
    cout << ans << '\n';
    return 0;
}