Cod sursa(job #2974002)

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

using namespace std;
long long int n,s,t,cost[10000005],kil[10000005],suma;
deque<long long 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;
}