Cod sursa(job #2292972)

Utilizator StanCatalinStanCatalin StanCatalin Data 30 noiembrie 2018 12:48:42
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <iostream>
#include <fstream>

using namespace std;

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

struct doua
{

    int c;
    int p;
};

int n,s,t,dq[100005];
doua a[100005];

int main()
{
    int i,suma = 0;
    int st = 0;
    int dr = -1;
    in >> n >> s >> t;
    for (i=1; i<=n; i++)
    {
        in >> a[i].c >> a[i].p;
    }
    suma += a[1].c * a[1].p;
    dq[++dr] = 1;
    t +=2 ;
    for (i=2; i<=n; i++)
    {
        if (st <= dr && dq[st] == i - t)
        {
            st++;
        }

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

        dq[++dr] = i;
        suma += (a[dq[st]].c + s * (i-dq[st])) * a[i].p;

    }
    out << suma;
    return 0;
}