Cod sursa(job #2731711)

Utilizator oana_mireaMirea Oana-Gabriela oana_mirea Data 28 martie 2021 02:13:53
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <iostream>
#include <fstream>

using namespace std;

void Push(int deq[],int &x,int nr)
{
    x++;
    deq[x]=nr;
}
void PopBack(int deq[],int &x)
{
    x--;
}
    int v[10000000],deq[10000000],p[10000000];
ifstream f("branza.in");
ofstream g("branza.out");
int main()
{

    int first=1, last=0;
     long long sum,n,t,s;
    f>>n>>s>>t;


    for(int i=1;i<=n;i++)
        f>>v[i]>>p[i];
    for(int i=1;i<=n;i++)
        {while((first<=last) &&(v[i]<=v[deq[last]]+s*(i-deq[last])))
            PopBack(deq,last);
        Push(deq,last,i);
        if(deq[first] == i-t-1)
            first++;
        sum+=(v[deq[first]]+s*(i-deq[first]))*p[i];
        }
    g<<sum;


    return 0;
}