Cod sursa(job #1907883)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 6 martie 2017 21:29:01
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
#include <deque>

using namespace std;

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

int n,s,t,i,c[100002],kg[100002],marime,ultimul;

long long suma;

deque <int> d;

int main()
{
    f>>n>>s>>t;
    for(i=1;i<=n;i++)
    {
        f>>c[i]>>kg[i];
    }
    //d.push_back(1);
    //suma+=c[1]*kg[1];
    for(i=1;i<=n;i++)
    {
        marime=d.size();
        ultimul=d.back();
        while((d.size()>0))
        {
            if(c[d.back()]+(i-d.back())*s>=c[i])
                d.pop_back();
            else
                break;
        }
        d.push_back(i);
        if(i-d.front()==t+1)
            d.pop_front();
        suma+=1LL*(c[d.front()]+(i-d.front())*s)*kg[i];
    }
    g<<suma;
    return 0;
}