Cod sursa(job #2322087)

Utilizator etienAndrone Stefan etien Data 17 ianuarie 2019 12:35:06
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.46 kb
#include <fstream>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
long long st,dr,i,n,k,v[100001],dq[100001],s,p;
long long sum;
int main()
{
    st=0;
    dr=-1;
    fin>>n>>s>>k;
    for(i=1; i<=n; ++i)
    {
        fin>>v[i]>>p;
        if(st<=dr&&dq[st]==i-k)
            st++;
        while(st<=dr&&v[i]<=v[dq[dr]]+s*(i-dq[dr]))
            dr--;
        dq[++dr]=i;
        sum+=(v[dq[st]]+s*(i-dq[st]))*p;
    }
    fout<<sum;
 }