Cod sursa(job #2582545)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 16 martie 2020 21:24:03
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>

using namespace std;

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

const int VM = 1e5;
long long d [VM + 1], pret [VM + 1];

int main() {
  long long n, s, t;
  long long cant, tot, alt, st, dr;
  in >> n >> s >> t;
  tot = dr = 0; st = 1;
  for (int i = 1; i <= n; i ++) {
    in >> pret [i] >> cant;
    while (st <= dr && pret [i] <= pret [d [dr]])
      dr --;
    d [++ dr] = i;
    if (d [dr] - d [st] == t)
      st ++;
    alt = cant * (pret [d [st]] + s * (d [dr] - d [st]));
    while (st < dr && alt >= cant * pret [i]) {
      st ++;
      alt = cant * (pret [d [st]] + s * (d [dr] - d [st]));
    }
    tot += alt;
  }
  out << tot;
  return 0;
}