Cod sursa(job #3170810)

Utilizator Mihnea07Rotaru Mihnea Mihnea07 Data 18 noiembrie 2023 10:15:05
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");

int main() {

 int n,t,s;
 in>>n>>s>>t;
 deque <int> dq;
 vector <int> cost(n+1);
 t++;
 int sum=0;
 for(int i=0;i<n;i++)
 {
     int cnt;
     in>>cost[i]>>cnt;
     if(!dq.empty() && dq.front()==i-t){
        dq.pop_front();
     }
     while(!dq.empty() && cost[i]<=cost[dq.back()]+(i-dq.back())*s)
     {
         dq.pop_back();
     }
     if(!dq.empty())
     {
         sum+=cnt*cost[dq.back()]+(i-dq.back())*s*cnt;
     }
     else{
        sum+=cnt*cost[i];
     }


     dq.push_back(i);

 }
 out<<sum;

    return 0;
}