Cod sursa(job #1832158)

Utilizator TincaMateiTinca Matei TincaMatei Data 19 decembrie 2016 15:44:10
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <cstdio>
typedef long long i64;

const int MAX_N = 100000;
struct Branza {
  int pret, cant, poz;
}v[MAX_N];

Branza duba[MAX_N];
int st, dr;

int main() {
  int n, s, t;
  long long costmin;
  FILE *fin = fopen("branza.in", "r");

  st = 0;
  dr = -1;
  costmin = 0LL;
  fscanf(fin, "%d%d%d", &n, &s, &t);
  for(int i = 0; i < n; ++i) {
    fscanf(fin, "%d%d", &v[i].pret, &v[i].cant);
    v[i].poz = i;
    if(i >= t && duba[st].pret == v[i - t].pret)
      ++st;
    while(dr >= st && v[i].pret < duba[dr].pret + (i - duba[dr].poz) * s)
      --dr;
    ++dr;
    duba[dr] = v[i];
    costmin = costmin + (i64)(duba[st].pret + (i - duba[st].poz) * s) * v[i].cant;
  }
  fclose(fin);

  FILE *fout = fopen("branza.out", "w");
  fprintf(fout, "%lld", costmin);
  fclose(fout);
  return 0;
}