Cod sursa(job #2939210)

Utilizator NanuGrancea Alexandru Nanu Data 13 noiembrie 2022 11:52:04
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda cnilc1_2-dq Marime 0.9 kb
#include <fstream>
#include <deque>
using namespace std;

ifstream fin("branza.in");
ofstream fout("branza.out");

#define DIM 100000
#define LL long long

int n;
LL s, t, cost[DIM + 1], kg[DIM + 1];
deque <int> DQ;

//DQ.front() retin cel mai bun pret pentru a putea produce un kg de branza;
//Deci elimin atat timp cat: cost[i] * kg[i] <= cost[DQ.back()] * kg[i] + (i - DQ.back()) * s * kg[i]; | :kg[i]
//cost[i] <= cost[DQ.back()] + (i - DQ.back()) * s;

int main() {
  fin >> n >> s >> t;

  LL total = 0;
  for(int i = 1; i <= n; i++) {
    fin >> cost[i] >> kg[i];

    while(!DQ.empty() && cost[i] <= cost[DQ.back()] + (i - DQ.back()) * s)
      DQ.pop_back();
    DQ.push_back(i);

    if(i - DQ.front() == t + 1)   //daca o tin de mai mult de t zile;
      DQ.pop_front();

    total += cost[DQ.front()] * kg[i] + (i - DQ.front()) * s * kg[i]; 
  }
  fout << total;

  return 0;
}