Cod sursa(job #2490960)

Utilizator ruxiTTutunaru Ruxandra ruxiT Data 11 noiembrie 2019 15:36:47
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <iostream>
#include <fstream>
const int N = 100001;

long long dq[N];
long long c[N];
long long p[N];

using namespace std;

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

int main()
{
    long long n, s, t, i, st = 1, dr = 0, sum = 0;
    fin >> n >> s >> t;
    for (i = 1; i <= n; i++)
        fin >> c[i] >> p[i];
    for (i = 1; i <= n; i++)
    {
        if (t + dq[st] < i)
            st++;
        while (dr >= st &&  c[i] <= c[dq[dr]]+(i - dq[dr]) * s)
            dr--;
        dq[++dr] = i;
        sum += c[dq[st]] * p[i] + s * (i-dq[st]) * p[i];
    }
    fout << sum;
    return 0;
}