Cod sursa(job #2832331)

Utilizator carinamariaCarina Maria Viespescu carinamaria Data 13 ianuarie 2022 14:20:11
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.5 kb
#include <fstream>
using namespace std;
ifstream cin("branza.in");
ofstream cout("branza.out");
long long n, s, t, st, dr, i, j, dq[100005], p[100005], c[100005], sum;
int main(){
    cin>>n>>s>>t;
    st=1;
    dr=0;
    for (i=1;i<=n;i++)
        cin>>c[i]>>p[i];
    for (i=1;i<=n;i++){
        while (st<=dr &&  c[i]<=c[dq[dr]]+(i-dq[dr])*s)
            dr--;
        dq[++dr]=i;
        if (t+dq[st]<i)
            st++;
        sum+=c[dq[st]]*p[i]+s*(i-dq[st])*p[i];
    }
    cout<<sum;
}