Cod sursa(job #3239801)

Utilizator Dia3141Costea Diana Stefania Dia3141 Data 7 august 2024 17:23:42
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#include <deque>
#define cost first
#define timp second
using namespace std;
ifstream cin("branza.in");
ofstream cout("branza.out");
int n,s,t,p,c;
long long sol;
deque<pair<int,int>>q;
int main()
{
    cin>>n>>s>>t;
    for(int i=1;i<=n;i++){
        cin>>p>>c;
        while(!q.empty()&&q.front().timp+t<i)
            q.pop_front();
        long long mini=1LL*p*c;
        if(!q.empty())
            mini=min(mini,1LL*(q.front().cost+s*(i-q.front().timp))*c);
        sol+=mini;
        int e=1;
        while(!q.empty()&&q.back().cost+s*e>=p){
            q.pop_back();
            e++;
        }
        q.push_back({p,i});
    }
    cout<<sol;
    return 0;
}