Cod sursa(job #3281492)

Utilizator jumaracosminJumara Cosmin-Mihai jumaracosmin Data 1 martie 2025 19:29:35
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>

std::ifstream fin("branza.in");
std::ofstream fout("branza.out");

const int size = 1e5 + 5;

int n, s, t;
int cost[size], demand[size];

std::deque<int> deque;

void read();
void solve();

int main()
{
    read();
    solve();
    return 0;
}

void read()
{
    fin >> n >> s >> t;
    for(int i = 1; i <= n; ++i)
        fin >> cost[i] >> demand[i];
}

void solve()
{
    int64_t ans = 0;

    for(int i = 1; i <= n; ++i)
    {
        // cat timp ne costa mai mult
        while(!deque.empty() && (cost[deque.back()] + s * (i - deque.back())) >= cost[i])
            deque.pop_back();
        // am gasit un index optim care poate fi folosit mai departe
        deque.push_back(i);
        // branza este expirata
        if(deque.front() < i - t)
            deque.pop_front();
        // adaug la costul total pretul minim pt ziua i
        ans += (int64_t) demand[i] * (cost[deque.front()] + s * (i - deque.front()));
    }

    fout << ans;

}