Cod sursa(job #2500079)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 27 noiembrie 2019 11:06:27
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda guritza Marime 1.14 kb
#include <cstdio>
#include <deque>

using namespace std;

const long long MAX_N = 100000;

struct Index {
  long long val;
  long long index;
};

long long n, s, t;
long long c[1 + MAX_N];
long long p[1 + MAX_N];
deque<Index> dq;

long long back_cost(long long i) {
  //fprintf(stderr, "%d %d\n", dq.back().val, dq.back().index);
  return 1LL * p[i + 1] * (dq.back().val + (i + 1 - dq.back().index) * s);
}

int main() {
  freopen("branza.in", "r", stdin);
  freopen("branza.out", "w", stdout);

  scanf("%lld%lld%lld", &n, &s, &t);
  for (long long i = 1; i <= n; i++) {
    scanf("%lld%lld", &c[i], &p[i]);
  }

  long long ans;

  ans = 1LL * p[1] * c[1];
  dq.push_back({c[1], 1});
  for (long long i = 2; i <= n; i++) {
    ans += min(1LL * p[i] * c[i], 1LL * p[i] * (dq.front().val + (i - dq.front().index) * s));

    if (i < n) {
      long long iCost = 1LL * p[i + 1] * (c[i] + s);
      while (dq.size() > 0 && iCost <= back_cost(i))
        dq.pop_back();
      dq.push_back({c[i], i});

      while (i - dq.front().index > t)
        dq.pop_front();
    }
  }

  printf("%lld\n", ans);
  return 0;
}