Cod sursa(job #2148069)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 1 martie 2018 15:14:26
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#define nmax 100005
using namespace std;
fstream f1("branza.in", ios::in);
fstream f2("branza.out", ios::out);
///eficient ori sa produci ori sa iei din depozit
int n, t,  coada[nmax], prim=1, ultim;
long long rez, cost[nmax], cant[nmax], s;
void citire()
{
    int i;
    f1>>n>>s>>t;
    for(i=1; i<=n; i++)
        f1>>cost[i]>>cant[i];
}
long long minim(long long a, long long b)
{
    return (a< b? a: b);
}
void solutie()
{
    int i; ///ordinea relativa di deque se pastreaza cu trecerea saptamanilor (toate cresc cu s)
    for(i=1; i<=n; i++)
    {
        if((prim<=ultim)&&(coada[prim]==i-t-1)) prim++;

        if(prim<=ultim) rez+=minim(cost[i], cost[coada[prim]]+ s*(i-coada[prim]))*cant[i];
        else rez+=cost[i]*cant[i];

        while((prim<=ultim)&&(cost[coada[ultim]]+ s*(i-coada[ultim]) > cost[i])) ultim--;
        ultim++;coada[ultim]=i;
    }
    f2<<rez;
}
int main()
{
    citire();
    solutie();
    return 0;
}