Cod sursa(job #1151415)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 24 martie 2014 09:26:07
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<fstream>
#define NMAX 100010

using namespace std;

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

struct branza
{
    long long pret, c;
}a[NMAX];

int n, T, p=1, u=1, d[NMAX];
long long best[NMAX], s;

void Citeste()
{
    int i;
    f>>n>>s>>T;
    for (i=1; i<=n; ++i)
        f>>a[i].pret>>a[i].c;
}

void Solve()
{
    int i;

    best[1]=a[1].c*a[1].pret; d[1]=1;
    for (i=2; i<=n; ++i)
    {
        if (d[p]==i-T-1) ++p;

        while(u>=p && a[d[u]].pret+(i-d[u])*s>=a[i].pret)
            --u;
        d[++u]=i;

        best[i]=best[i-1]+(a[d[p]].pret+(i-d[p])*s)*a[i].c;
    }

    g<<best[n]<<"\n";
}

int main()
{
    Citeste();
    Solve();
    f.close();
    g.close();
    return 0;
}