Cod sursa(job #1290320)

Utilizator cristinamateiCristina Matei cristinamatei Data 11 decembrie 2014 09:19:03
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>

using namespace std;

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

int n, s, t, a[100001], cost[100001], dq[100001], st, dr;

void stanga( int i )
{
    if ( i - dq[st] > t )
        st++;
}

void dreapta( int i )
{
    while ( st <= dr && a[i] < a[ dq[dr] ] + s * ( i - dq[dr] ) )
        dr--;
    dq[++dr] = i;
}

int main()
{
    int i;
    long long nr = 0;
    in >> n >> s >> t;
    for ( i = 1; i <= n; i++ )
        in >> a[i] >> cost[i];
    dq[++st] = 1;
    dq[++dr] = 1;
    nr = a[1] * cost[1];
    for ( i = 2; i <= n; i++ )
    {
        stanga(i);
        dreapta(i);
        nr+= ( a[ dq[st] ] + s * ( i - dq[st] ) ) * cost[ i ];
    }
    out << nr;
    return 0;
}