Cod sursa(job #2801850)

Utilizator vlad_dimuVlad Dimulescu vlad_dimu Data 16 noiembrie 2021 22:56:32
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <fstream>
#include <deque>
#define MAXN 100000
using namespace std;

ifstream fin( "branza.in" );
ofstream fout( "branza.out" );

long long pret[MAXN + 1];

deque <long long> d;

int main(){
  long long n, s, t, i, kg, sum;
  fin >> n >> s >> t;
  t++;
  sum = 0;
  for( i = 0; i < n; i++ ){
    fin >> pret[i] >> kg;
    if( !d.empty() && d.front() == i - t )
      d.pop_front();

    while( !d.empty() && (pret[d.back()] + s * ( i - d.back() )) >= pret[i] )
      d.pop_back();
    d.push_back(i);
    sum += ( pret[d.front()] + s * (i - d.front())) * kg;
  }
  fout << sum;
  return 0;
}