Cod sursa(job #2205478)

Utilizator sydeff90Voicu Stefan sydeff90 Data 19 mai 2018 11:43:32
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <deque>
#include <iostream>
#include <fstream>

using namespace std;
struct elem {
  int val, poz;
};

deque<elem> d;


int main() {
  ifstream in("deque.in");
  ofstream out("deque.out");
  long long n, k, val, s=0;
  elem aux;
  in>>n>>k;
  for (int i=1; i<=n; i++) {
    in >> val;
    aux.val=val;
    aux.poz=i;
    if(i<=k)
    {

      while(!d.empty()&&d.back().val>aux.val)
        d.pop_back();
      d.push_back(aux);
      if(i==k)
        s=d.front().val;

    }
    else
    {
      while(!d.empty()&&d.front().poz<i-k+1)
        d.pop_front();
       while(!d.empty()&&d.back().val>aux.val)
        d.pop_back();
      d.push_back(aux);
      s+=d.front().val;


    }
  }
   out<<s;
  return 0;
}