Cod sursa(job #2648145)

Utilizator Robert975Robert Robert975 Data 8 septembrie 2020 22:33:32
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.55 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
  int v[5000010], i, n, k, sum = 0;

int main () {
  //int v[5000], i, n, k, sum = 0;
  deque <int> q;
  fin>>n>>k;

  for (i = 1; i <= n; i++)
    fin>>v[i];

  for (i = 1; i <= n; i++) {
    while (!q.empty() && v[i] <= v[q.back()])
      q.pop_back();

    q.push_back(i);

    if (q.front() == i - k + 1) {
      sum += v[q.front()];
      q.pop_front();
    }
  }
  sum += v[q.front()];
  fout<<sum;
}