Cod sursa(job #1978719)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 8 mai 2017 17:54:56
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <cstdio>

typedef long long i64;
const int MAXN = 1e5;

int v[MAXN + 1], po[MAXN + 1];

int main() {
  int n, s, t, pz, u, cost, c, p;
  i64 sol;
  FILE *f = fopen("branza.in", "r");
  fscanf(f, "%d%d%d", &n, &s, &t);
  sol = u = 0;
  pz = 1;
  for (int i = 1; i <= n; ++i) {
    fscanf(f, "%d%d", &cost, &p);
    v[i] = cost - i * s;
    while ((pz <= u) && (v[i] <= v[po[u]])) {
      --u;
    }
    po[++u] = i;
    sol += 1LL * p * (v[po[pz]] + i * s);
    if (po[pz] + t == i) {
      ++pz;
    }
  }
  fclose(f);
  f = fopen("branza.out", "w");
  fprintf(f, "%lld\n", sol);
  fclose(f);
  return 0;
}