Cod sursa(job #3369915)

Utilizator Maryy_1369Gociu Maria Anastasia Maryy_1369 Data 22 octombrie 2026 13:37:57
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include<deque>
using namespace std;

ifstream cin("branza.in");
ofstream cout("branza.out");

long long c[100002];
long long p[100002];
long long a[100002];
int main()
{
    int n,t,s;
    cin>>n>>s>>t;
    for(int i=1;i<=n;i++){
        cin>>c[i]>>p[i];
        a[i]=c[i]-s*i;
    }
    deque<int>dq;
    long long ans=0;
    for(int i=1;i<=n;i++){
        while(!dq.empty() && i-dq.front()>t)dq.pop_front();//scoatem ce a depasit t sapt

        while(!dq.empty() && a[dq.back()]>=a[i])dq.pop_back();//scoatem ce e mai mare aka nu poate fi mini

        dq.push_back(i);
        ans+=p[i]*(a[dq.front()]+s*i);
    }
    cout<<ans;
    return 0;
}

/*
dc producem un kg in sap j si il folosim in sap i -> cost = cj + s(i-j) = cj+ si + sj

si este la fel pt toate sapt anterioare -> j trb sa fie minim -> cj - sj minim

a j = cj-sj -> kg minim pt sapt i = min(aj)+si
i-j<=t -> in dq eliminam cat timp i-dq.fornt > t (nu mai pot fi pastrate)

eliminam din spate val care sunt mai mari sau egale cu cea curenta -> nu mai pot fi minime

dupa astea 2 => costul sapt i = pi*(a[dq.front] + si)
*/