Cod sursa(job #2133233)

Utilizator antracodsAntracod antracods Data 16 februarie 2018 18:24:36
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

deque <long int> myDeck;

const int NMAX = 100000;

int n,s,t; /// Saptamani, Storage cost, Expiration
int cost[NMAX+2];
int cantitate[NMAX+2];
long long int sol = 0;

void remove_expired(int i)
{
    while(myDeck.empty()==0 && i-myDeck.front()>t)
    {
        myDeck.pop_front();
    }
}

void add_week(int i)
{
    while(myDeck.empty()==0 && cost[myDeck.back()]+(i-myDeck.back())*s>=cost[i])
    {
        myDeck.pop_back();
    }
    myDeck.push_back(i);
}

void add_cost(int i)
{
    sol+=1LL*(1LL*cost[myDeck.front()]*cantitate[i]+1LL*(i-myDeck.front())*s*cantitate[i]);
}

int main()
{
    in>>n>>s>>t;
    for(int i=1;i<=n;i++)
    {
        in>>cost[i]>>cantitate[i];
    }

    for(int i=1;i<=n;i++)
    {
        remove_expired(i);
        add_week(i);
        add_cost(i);
    }
    out<<sol;
    return 0;
}