Cod sursa(job #2499180)

Utilizator Rares31100Popa Rares Rares31100 Data 25 noiembrie 2019 16:58:05
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>

using namespace std;

ifstream cin("branza.in");
ofstream cout("branza.out");

int n,s,t;
int cost[100001],buc[100001];
int coada[100001],last,vf;
long long sum_tot;

void citire()
{
    cin>>n>>s>>t;

    for(int i=1;i<=n;i++)
        cin>>cost[i]>>buc[i];
}

int val(int poz,int i)
{
    return cost[ coada[poz] ]+s*(i-coada[poz]);
}

int main()
{
    citire();

    last++;
    for(int i=1;i<=n;i++)
    {
        while(last<=vf && coada[last]<i-t)
            last++;

        while(vf>=last && val(vf,i)>=cost[i] )
            vf--;

        coada[++vf]=i;

        sum_tot+=(long long)val(last,i)*buc[i];
    }

    cout<<sum_tot;
}