Cod sursa(job #2177371)

Utilizator Iulia25Hosu Iulia Iulia25 Data 18 martie 2018 14:45:33
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <deque>

using namespace std;

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

const int inf = 0x3f3f3f3f;

deque <int> p, q;
int n, k, i, a, suma;

int main()  {
  fin >> n >> k;
  for (i = 1; i <= k; ++i)  {
    fin >> a;
    while (!q.empty() && q.back() >= a) {
      q.pop_back();
      p.pop_back();
    }
    q.push_back(a);
    p.push_back(i);
  }
  suma += q.front();
  for (i = k + 1; i <= n; ++i)  {
    fin >> a;
    while (!q.empty() && q.back() >= a) {
      q.pop_back();
      p.pop_back();
    }
    q.push_back(a);
    p.push_back(i);
    while (p.front() <= i - k)  {
      p.pop_front();
      q.pop_front();
    }
    suma += q.front();
  }
  fout << suma;
}