Cod sursa(job #2803052)

Utilizator Theodor17Pirnog Theodor Ioan Theodor17 Data 19 noiembrie 2021 12:34:16
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
#include <deque>
#define ll long long

using namespace std;

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

const int NMAX = 1e5;
long long c[NMAX + 1], p[NMAX + 1], ans, n, s, t;
deque <int> dq;

void read(){

    cin >> n >> s >> t;
    for(int i = 1; i <= n; i++)
        cin >> c[i] >> p[i];

}

void solve(){

    for(int i = 1; i <= n; i++){

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

        dq.push_back(i);

        while(!dq.empty() && dq.front() < i - t)
            dq.pop_front();    

        ans += p[i] * (c[dq.front()] + s * (i - dq.front()));    

    }

    cout << ans;
  
}

int main(){

    read();
    solve();

}