Cod sursa(job #2724192)

Utilizator MihaiLazar26Lazar Mihai MihaiLazar26 Data 16 martie 2021 18:09:00
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;

ifstream fin("branza.in");
ofstream fout("branza.out");

int main()
{
    int n, s, t, *c, *p, mins=0, F=1, B=0, *deq;
    fin>>n>>s>>t;
    c = new int[n+10];
    p = new int[n+10];
    deq = new int[n+10];
    for(int i=1; i<=n; i++)
        fin>>c[i]>>p[i];


    for(int i=1; i<=n; i++)
    {
        while(F<=B && c[i] <= c[deq[B]]+(i-deq[B])*s) B--;

        deq[++B]=i;
        if(i-deq[F]>t) F++;

        mins+=p[i]*(c[deq[F]]+(i-deq[F])*s);
    }

    fout<<mins;

    delete[] c;
    delete[] p;
    delete[] deq;
}