Cod sursa(job #2888697)

Utilizator PatrascuAdrian1Patrascu Adrian Octavian PatrascuAdrian1 Data 11 aprilie 2022 19:17:22
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
//comentarii in caz ca ma pune cineva sa explic solutia si sunt prea obosit sa-mi aduc aminte
//buna
#include <bits/stdc++.h>

using namespace std;

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

int main()
{
    long long N, T, S;
    in >> N >> S >> T;
    long long C[N + 1], P[N + 1];
    for(int i = 1; i <= N; ++i)
        in >> C[i] >> P[i];
    long long ans = 0;
    deque<int> D;
    for(int i = 1; i <= N; ++i)
    {
        while(!D.empty() && D.front() + T < i) // eliminam indicii expierati
            D.pop_front();
        while(!D.empty() && C[D.back()] + S * (i - D.back()) > C[i]) // eliminam indecsi cat timp nu merita sa facem branza in saptamanile alea
            D.pop_back();
        D.push_back(i);
        ans += P[i] * (C[D.front()] + (i - D.front()) * S);
    }
    out << ans;
    return 0;
}
//pa