Cod sursa(job #3337378)

Utilizator Luca_georgescuLuca Georgescu Luca_georgescu Data 27 ianuarie 2026 15:49:50
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("branza.in");
ofstream g("branza.out");

const int nmax=1e7+5;
int n,s,t,c[nmax],p[nmax];

int main()
{
    f >> n >> s >> t;

    for (int i=1; i<=n; i++ )
        f >> c[i] >> p[i];

    // intrebarea fiecarei saptamani este:
    // daca vindem un produs mai tarziu decat trebuia (initial sapt era i, dar vindem in sapt j
    // costul per kg devine: c[i]+s*(j-i)=c[i]+s*j+s*i //costul lui + cost de depozistare
    // pt o sapt fixa j, tb sa alegem i din (j-t,j), astfel incat sa minimizam costul per kg

    deque <int> dq;
    int ans=0;

    for (int j=1; j<=n; j++ )
    {
        while ( !dq.empty() && (j-dq.front())>t )
            dq.pop_front();

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

        dq.push_back(j);

        ans+=p[j]*c[dq.front()]+s*p[j]*(j-dq.front());
    }

    g << ans;
    return 0;
}