Cod sursa(job #2153684)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 6 martie 2018 13:35:08
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream in("deque.in");
ofstream out("deque.out");

struct numar{
  long long int poz;
  long long int val;

  numar (long long int _a = 0, long long int _b = 0){
    poz = _a;
    val = _b;
  }
};

deque <numar>minime;
int n, k;

int main(){
  in >> n >> k;

  for (int i = 1; i < k; ++ i){
    numar nr;
    in >> nr.val;
    nr.poz = i;

    if (minime.size())
      while (minime.back().val >= nr.val && minime.size())
        minime.pop_back();
    minime.push_back(nr);
  }

  long long int suma_min = 0;

  for (int i = k; i <= n; ++ i){
    numar nr;
    in >> nr.val;
    nr.poz = i;

    if (minime.front().poz < i - k + 1)
      minime.pop_front();

    if (minime.size())
      while (minime.back().val >= nr.val && minime.size())
        minime.pop_back();
    minime.push_back(nr);

    suma_min += minime.front().val;
  }

  out << suma_min;


  return 0;
}