Cod sursa(job #1054026)

Utilizator cristigrigoreGrigore Cristan Andrei cristigrigore Data 13 decembrie 2013 11:18:09
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <cstdio>
#include <deque>
using namespace std;
deque < int > q;
int i,j,n,m,k,x,a[5000005];
long long s;
int main()
{
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);
    scanf("%d %d\n",&n,&k);
    for(i=1; i<=n; i++)
    {
        scanf("%d\n",&a[i]);
        while(!q.empty()&&a[q.back()]>a[i])
        {
            q.pop_back();
        }
        q.push_back(i);
        while(q.front()<=i-k)
        {
            q.pop_front();
        }
        if(i>=k)
        {
            s+=a[q.front()];
        }
    }
    printf("%lld\n",s);

    return 0;
}