Cod sursa(job #2454546)

Utilizator urweakurweak urweak Data 8 septembrie 2019 22:28:54
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <bits/stdc++.h>
#define nmax 100000
using namespace std;

deque <int> d;
int cost[nmax], kg[nmax];

  
int N, pretS, S;
long long ans;

int main(){
  ifstream in("branza.in");
  ofstream out("branza.out");
  in >> N >> pretS >> S;
  for(int i = 0; i<N; i++){
    in >> cost[i] >> kg[i];

    while(!d.empty() && cost[d.back()] + 1LL * (i - d.back()) * pretS > cost[i]) d.pop_back();
    d.push_back(i);
    
    if(i - d.front() > S) d.pop_front();
    
    ans+=(cost[d.front()] + 1LL * (i - d.front()) * pretS) * kg[i];
  }
  out << ans;
  return 0;
}