Cod sursa(job #2731837)

Utilizator vlad_dimaVlad Dima vlad_dima Data 28 martie 2021 13:48:34
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <bits/stdc++.h>

using namespace std;

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

    deque <int> dq;
    long long sum = 0, n, t, c[100000], p;
    int s;

    fin>>n>>s>>t;

    for (int i = 0; i < n; i++)
    {

        if (i - dq.front() > t)
            dq.pop_front();

        fin>>c[i]>>p;

        if (dq.empty())
            dq.push_back(i);

        while (!dq.empty() && c[i] < c[dq.back()] + s * (i - dq.back()))
            dq.pop_back();
        dq.push_back(i);

        sum += p * (c[dq.front()] + s * (i - dq.front()));
    }
    fout<<sum;
    fin.close();
    fout.close();
}