Cod sursa(job #2725948)

Utilizator PopescuMihneaPopescu Mihnea-Valentin PopescuMihnea Data 19 martie 2021 21:50:25
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("branza.in");
ofstream g ("branza.out");
int coada[100000],cantitate[100000],zi[100000];
int main()
{
    int N,S,T,C,P,i,j,st,dr,pret_zi;
    st=dr=0;
    long long cost=0;
    f>>N>>S>>T;
    for (i=0; i<N; i++)
    {
        f>>C>>P;
        while (C<=coada[dr-1] && dr-1>=st)
            dr--;
        coada[dr]=C;
        zi[dr]=i;
        cantitate[dr++]=P;
        while (i-zi[st]>T && st+1<=dr)
            st++;
        pret_zi=C*P;
        for (j=st; j<dr-1; j++)
            if (C*P>coada[j]*P+P*S*(i-zi[j]))
                pret_zi=coada[j]*P+P*S*(i-zi[j]);
        cost+=pret_zi;
    }
    g<<cost;
}