Cod sursa(job #893057)

Utilizator visanrVisan Radu visanr Data 26 februarie 2013 12:49:36
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <deque>
using namespace std;

#define Nmax 5000010

deque<int> D;
int N, K, V[Nmax];
long long Sum;

int main()
{
    freopen("deque.in", "r", stdin);
    freopen("deque.out", "w", stdout);
    int i;
    scanf("%i %i", &N, &K);
    for(i = 1; i <= N; ++ i) scanf("%i", &V[i]);
    for(i = 1; i <= N; ++ i)
    {
        while(!D.empty() && V[D.back()] >= V[i]) D.pop_back();
        D.push_back(i);
        while(!D.empty() && D.front() <= i - K) D.pop_front();
        if(D.size() && i >= K) Sum += 1LL * V[D.front()];
    }
    printf("%lld\n", Sum);
    return 0;
}