Cod sursa(job #946935)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 6 mai 2013 13:17:31
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <deque>

using namespace std;

int main()
{
    ifstream cin("branza.in");
    ofstream cout("branza.out");

    deque <int> coada;
    int cost[100005],produs[100005];
    int n,s,t,i;
    cin>>n>>s>>t;

    t++;
    for(i=0;i<n;i++)
        cin>>cost[i]>>produs[i];

    long long int sum=0;

    for(i=0;i<n;i++)
    {
        while(!coada.empty())
            if(i-coada.front()>=t)
                coada.pop_front();
            else
                break;

        while(!coada.empty())
            if((cost[coada.back()]+(s*(unsigned long long int)(i-coada.back())))>=cost[i])
               coada.pop_back();
            else
               break;

        coada.push_back(i);

        //cout<<(cost[coada.front()]+s*(i-coada.front()))*produs[i]<<endl;
        sum+=((cost[coada.front()]+s*(i-coada.front()))*produs[i]);
    }
    cout<<sum<<'\n';

    cin.close();
    cout.close();
    return 0;
}