Cod sursa(job #2742791)

Utilizator As932Stanciu Andreea As932 Data 21 aprilie 2021 19:40:00
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
#include <deque>
#define ll long long

using namespace std;

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

const int nmax = 1e5 + 5;

int n, s, t;
ll ans;
pair <ll, ll> v[nmax];

void read(){
    cin >> n >> s >> t;

    for(int i = 1; i <= n; i++)
        cin >> v[i].first >> v[i].second;
}

void solve(){
    deque <int> d;

    for(int i = 1; i <= n; i++){
        while(!d.empty() && i - d.front() > t)
            d.pop_front();

        while(!d.empty() && v[i].first <= v[d.back()].first + (i - d.back()) * s * 1LL)
            d.pop_back();

        d.push_back(i);

        ans += ((v[d.front()].first + (i - d.front()) * s * 1LL) * v[i].second * 1LL);
    }

    cout << ans;
}

int main()
{
    read();
    solve();

    return 0;
}