Cod sursa(job #1604756)

Utilizator AntoniooMacovei Antonio Antonioo Data 18 februarie 2016 15:53:04
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <stdio.h>
#include <deque>
using namespace std;
deque <int> d;
int v[5000001];
int main()
{
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);
    int n, i, k;
    long long s = 0;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++)
    {
      scanf("%d",&v[i]);
      while(!d.empty() && v[d.back()]>=v[i]){
        d.pop_back();
      }
      d.push_back(i);
      if(i>=k) {
        if(d.back()-d.front()+1 > k ) {
          d.pop_front();
        }
        s += v[d.front()];
      }

    }
     printf("%lld",s);
    return 0;
}