Cod sursa(job #2799193)

Utilizator vlad2009Vlad Tutunaru vlad2009 Data 12 noiembrie 2021 16:59:31
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <deque>

using namespace std;

const int Nmax = 1e5;
long long c[1 + Nmax], p[1 + Nmax];
deque<long long> dq;

int main() {
  ifstream fin("branza.in");
  ofstream fout("branza.out");
  long long n;
  long long s, t;
  fin >> n >> s >> t;
  for (int i = 1; i <= n; i++) {
    fin >> c[i] >> p[i];
  }
  long long ans = 0;
  for (long long i = 1; i <= t; i++) {
    while (!dq.empty() && c[dq.back()] + (i - dq.back()) * s >= c[i]) {
      dq.pop_back();
    }
    dq.push_back(i);
    ans += (c[dq.front()] + (i - dq.front()) * s) * p[i];
  }
  for (long long i = t + 1; i <= n; i++) {
    if (!dq.empty() && dq.front() + 1 == i - t) {
      dq.pop_front();
    }
    while (!dq.empty() && (c[dq.back()] + (i - dq.back()) * s) * p[i] >= c[i] * p[i]) {
      dq.pop_back();
    }
    dq.push_back(i);
    ans += (c[dq.front()] + (i - dq.front()) * s) * p[i];
  }
  fout << ans;
  return 0;
}