Cod sursa(job #1832145)

Utilizator TincaMateiTinca Matei TincaMatei Data 19 decembrie 2016 15:29:48
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <cstdio>
typedef unsigned 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");
  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;
  }
  fclose(fin);

  st = 0;
  dr = -1;
  costmin = 0LL;
  for(int i = 0; i < n; ++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;
  }

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