Cod sursa(job #2205463)

Utilizator raduqRadu Minea raduq Data 19 mai 2018 11:16:26
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<iostream>
#include<cstdio>
#include<deque>
using namespace std;
struct elem
{ int val, poz; };
deque<elem>d;
elem aux;
int n,k,s,i,x;
int main()
{
  freopen("deque.in","r",stdin);
  freopen("deque.out","w",stdout);
  cin>>n>>k;
  cin>>x;
  aux.val=x; aux.poz=1;
  d.push_back(aux);
  for(i=2; i<=k; i++)
  {
    cin>>x;
    while(x<d.back().val){ d.pop_back(); }
    aux.val=x; aux.poz=i;
    d.push_back(aux);
  }
  s+=d.front().val;
  for(i=k+1; i<=n; i++)
  {
    if(d.front().poz<=i-k) d.pop_front();
    cin>>x;
    while(x<d.back().val){ d.pop_back(); }
    aux.val=x; aux.poz=i;
    d.push_back(aux);
    s+=d.front().val;
  }
  cout<<'\n'<<s;
  return 0;
}