Cod sursa(job #2717990)

Utilizator rapidu36Victor Manz rapidu36 Data 8 martie 2021 12:03:07
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>

using namespace std;

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

const int N = 100005;

long long p[N];
int d[N], c[N];

int main ()
{
    int n, s, t, st, dr, i;
    long long af;
    in >> n >> s >> t;
    for (i = 1; i <= n; i++)
        in >> c[i] >> p[i];
    st = dr = 1;
    d[1] = 1;
    af = c[1] * p[1];
    for (i = 2; i <= n; i++)
    {
        while (st <= dr && c[i] <= (i - d[dr]) * s + c[d[dr]])
            dr--;
        dr++;
        d[dr] = i;
        if (i - t == d[st] + 1)
            st++;
        af += (c[d[st]] + s * (i - d[st])) * p[i];
    }
    out << af;

    return 0;
}