Cod sursa(job #3289482)

Utilizator rapidu36Victor Manz rapidu36 Data 27 martie 2025 09:13:10
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>

using namespace std;

const int N = 1e5;

int pret[N], dq[N];

int main()
{
    ifstream in("branza.in");
    ofstream out("branza.out");
    int n, s, k;
    long long s_tot = 0;
    in >> n >> s >> k;
    k++;
    int st = 0, dr = -1;
    for (int i = 0; i < n; i++)
    {
        int cant;
        in >> pret[i] >> cant;
        while (st <= dr && pret[i] <= pret[dq[dr]] + s * (i - dq[dr]))
        {
            dr--;
        }
        dq[++dr] = i;
        if (dq[st] == i - k)
        {
            st++;
        }
        s_tot += (long long)cant * (pret[dq[st]] + s * (i - dq[st]));
    }
    out << s_tot << "\n";
    in.close();
    out.close();
    return 0;
}