Cod sursa(job #3136581)

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

using namespace std;

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

void solve()
{
    for(int 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;
}