Cod sursa(job #2889197)

Utilizator elenaaa15Dobre Elena elenaaa15 Data 12 aprilie 2022 14:02:47
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <bits/stdc++.h>

using namespace std;

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

int main()
{
    long long N, T;
    int S,i;
    f >> N >> S >> T;

    long long cost[N + 1], P[N + 1];
    for(i = 0; i < N; i++)
        f >> cost[i] >> P[i];

    long long smin = 0;

    deque<int> branza;

    for(i = 0; i<N;i++)
    {
        while(!branza.empty() && branza.front() + T < i) //pop daca branza a expirat
            branza.pop_front();

        while(!branza.empty() && cost[branza.back()] + S * (i - branza.back()) > cost[i]) //pop daca costul e mai mare decat
            branza.pop_back();

        branza.push_back(i);

        smin += P[i] * (cost[branza.front()] + (i - branza.front()) * S);
    }

    g << smin;

    f.close();
    g.close();
    return 0;
}