Cod sursa(job #2445554)

Utilizator toadehuPuscasu Razvan Stefan toadehu Data 4 august 2019 16:22:18
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.59 kb
#include <bits/stdc++.h>

using namespace std;

long long int cant,cost[100009],best[100009],ans,n,s,t,last=-1,first;

int main()
{
    ifstream fin("branza.in");
    ofstream fout("branza.out");
    fin>>n>>s>>t;
    for(int i=1; i<=n; ++i)
    {
        fin>>cost[i]>>cant;
        if(best[first]==i-t-1)
        {
            first++;
        }
        while(first<=last&&cost[i]<=(cost[best[last]]+(i-best[last])*s))
        {
            last--;
        }
        best[++last]=i;
        ans+=cant*(cost[best[first]]+((i-best[first])*s));
    }
    fout<<ans;
    return 0;
}