Cod sursa(job #1125146)

Utilizator gabrielvGabriel Vanca gabrielv Data 26 februarie 2014 15:55:13
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <cstdio>
#include <vector>
#include <deque>

using namespace std;

int N,K;
long long Sol;

vector < int > V;
deque < int > Deque;

int main()
{
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);

    scanf("%d%d",&N,&K);

    V.resize(N+1);

    for(int i=1;i<=N;i++)
        scanf("%d",&V[i]);

    for(int i=1;i<=N;i++)
    {
        while(Deque.size() && V[Deque.back()] >= V[i])
            Deque.pop_back();

        Deque.push_back(i);

        if(Deque.front() == i-K)
            Deque.pop_front();

        if(i>=K)
            Sol += V[Deque.front()];
    }

    printf("%lld\n",Sol);

    return 0;
}