Cod sursa(job #2152325)

Utilizator dimi999Dimitriu Andrei dimi999 Data 5 martie 2018 13:56:17
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.51 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");

int v[100005],dq[100005];

int main()
{
    long long n,s,t,st=1,dr=0,cant,pret,sum=0;
    int i=1;
    fin>>n>>s>>t;
    while(i<=n)
    {
        fin>>v[i]>>pret;
        if(dq[st]==i-t)
            st++;
        while(st<=dr&&(v[i]-s*(i-dq[dr]))<=v[dq[dr]])
            dr--;
        dq[++dr]=i;
        sum=sum+pret*(v[dq[st]]+s*(i-dq[st]));
        i++;
    }
    fout<<sum;
    return 0;
}