Cod sursa(job #1893999)

Utilizator SenibelanMales Sebastian Senibelan Data 26 februarie 2017 12:50:56
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <deque>
#define NMAX 5000005

using namespace std;

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

int N, K;
int nr;
int suma;
vector <int> v(NMAX);
deque  <int> d;

void Read(){
  in >> N >> K;
  for(int i = 1; i <= N; ++i){
    in >> nr;
    v[i] = nr;
  }
}

void Solve(){
  for(int i = 1; i <= N; ++i){
    nr = v[i];
    while(!d.empty() && nr <= v[d.back()])
      d.pop_back();
    d.push_back(i);
    if(i - d.front() >= K)
        d.pop_front();
    if(i >= K)
      suma += v[d.front()];
  }
  out << suma << "\n";
}

int main() {
  Read();
  Solve();
  return 0;
}