Cod sursa(job #3339207)

Utilizator NeamtuMateiNeamtu Matei-Constantin NeamtuMatei Data 6 februarie 2026 20:01:31
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

#define in fin
#define out fout
#define int long long
ifstream fin("branza.in");
ofstream fout("branza.out");

const int MAXN = 1e5;

int n, s, t, total;
int cost[MAXN+1], cerere[MAXN+1];
deque<int> dq;

signed main() {
    in >> n >> s >> t;
    for (int i = 1; i <= n; i++)
        in >> cost[i] >> cerere[i];

    // costul pastrarii unei branze de la ziua i la ziua j este
    // cost[i] + s * (j - i). in intervalul (i - t, i) cautam minimul dupa formula aia
    for (int i = 1; i <= n; i++) {
        while (!dq.empty() && dq.front() < i - t)
            dq.pop_front();

        while (!dq.empty() && cost[i] <= cost[dq.back()] + s * (i - dq.back()))
            dq.pop_back();

        dq.push_back(i);

        total += cost[dq.front()] * cerere[i] + s * cerere[i] * (i - dq.front());
    }

    out << total;

    return 0;
}