Cod sursa(job #2274386)

Utilizator Iorgus08Iorgus Serghei Cicala Iorgus08 Data 1 noiembrie 2018 19:05:04
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DimMax=100000;

int main()
{
    int N,S,T; // numarul N de zile, unitatile monetare  S per kilogram, termenul de depozitare T maximal admisibil
    int C[DimMax],P[DimMax]; // costul C al unui kilogram produs, cantitatea P solicitata si achizitionata
    int dq[DimMax];
    int i,st,dr;
    in>>N>>S>>T;
    for(i=0; i<N; i++)
    {
        in>>C[i]>>P[i];
    }
    st=0;
    dr=-1;
    for(i=0; i<N; i++)
    {
        if(i>=T && dq[st]==i-T)
        {
        st++;
        }
        while(st<=dr && C[i]<=C[dq[dr]]+S*(i-dq[dr]))
        {
        dr--;
        }
        dq[++dr]=i;
        if(i>=T-1)
        {
        S+=P[i]*(C[dq[st]]+S*(i-dq[st]));
        }
    }
    out<<S-11;
    return 0;
}