Cod sursa(job #2973999)

Utilizator VertimaXxFlorea Vlad VertimaXx Data 2 februarie 2023 21:32:04
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <bits/stdc++.h>

using namespace std;
int n,s,t,cost[10000005],kil[10000005],suma;
deque<int> dechiu;

int main()
{
    ifstream cin("branza.in");
    ofstream cout("branza.out");
    cin >> n >> s >> t;
    for(int i=1;i<=n;i++)
    {
        cin >> cost[i] >> kil[i];
    }
    for(int i=1;i<=n;i++)
    {
        if(!dechiu.empty() && dechiu.front() == i-t-1)
        {
            dechiu.pop_front(); //nu se afla intr-un interval bun pentru depozit
        }
        while(!dechiu.empty() && cost[i] < (cost[dechiu.back()] + s*(i-dechiu.back()))) // elementele mici scot elementele mari, calculam si pt depozity
        {
            dechiu.pop_back();
        }
        dechiu.push_back(i);
        suma += kil[i] * (cost[dechiu.front()] + s*(i-dechiu.front()));
    }
    cout << suma;
}