Cod sursa(job #3136587)

Utilizator TeodoraMaria123Serban Teodora Maria TeodoraMaria123 Data 6 iunie 2023 23:53:34
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;

struct week
{
    long long cost, p;
};
long long n, s, t;
long long ans;
vector <week> weeks;
deque <long long> minNumbers;

void solve()
{
    for(long long i = 1; i <= n; i++)
    {
        if(!minNumbers.empty()  &&  minNumbers.front() <= i - t)
            minNumbers.pop_front();

        while(!minNumbers.empty()  &&  weeks[minNumbers.back()].cost * weeks[i].p + weeks[i].p * s * (i - minNumbers.back())> weeks[i].p * weeks[i].cost)
            minNumbers.pop_back();
        minNumbers.push_back(i);

        ans += weeks[minNumbers.front()].cost * weeks[i].p + weeks[i].p * s * (i - minNumbers.front());
    }

    cout << ans;
}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    freopen("branza.in", "r", stdin);
    freopen("branza.out", "w", stdout);

    cin >> n >> s >> t;
    weeks.resize(n + 1);
    for(int i = 1; i <= n; i ++)
        cin >> weeks[i].cost >> weeks[i].p;

    solve();
    return 0;
}