Cod sursa(job #1186096)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 17 mai 2014 11:59:17
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>

using namespace std;

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

int s , t , c[100001] , p[100001] , coada[100001] , st , dr;

inline void stanga(int i)
{
    if(i - t == coada[st])
        st++;
}

inline void dreapta(int i)
{
    while(st <= dr && c[i] < c[coada[dr]] + s * (i - coada[dr]))
        dr--;

    coada[++dr] = i;
}

int main()
{
    int n , i;

    long long sum;

    in>>n>>s>>t;

    t++;

    for(i = 1 ; i <= n ; i++)
        in>>c[i]>>p[i];

    st = 1;
    dr = 0;
    sum = 0;

    for(i = 1 ; i <= n ; i++)
    {
        if(i >= t) stanga(i);
        dreapta(i);

        sum += (long long)c[coada[st]] * p[i] + (long long)s * (i - coada[st]) * p[i];

    }

    out<<sum<<'\n';
    return 0;
}