Cod sursa(job #2320847)

Utilizator mariaghinescu22Ghinescu Maria mariaghinescu22 Data 15 ianuarie 2019 10:50:30
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.49 kb
#include <iostream>

using namespace std;

int main(){
    long long c[100001], p[100001], n, s, t, st=0, dr=-1, dq[100001], rez=0;
    cin>>n>>s>>t;
    t++;
    for(int i=0; i<n; i++){
        cin>>c[i]>>p[i];
    }
    for(int i=0; i<n; i++){
        if(st<=dr && dq[st]==(i-t)){
            st++;
        }
        while(st<=dr && c[i]<=c[dq[dr]]+(i-dq[st])*s){
            dr--;
        }
        dq[++dr]=i;
        rez=rez+(c[dq[st]]+(i-dq[st])*s)*p[i];
    }
    cout<<rez;
    return 0;
}