Cod sursa(job #1016759)

Utilizator sziliMandici Szilard szili Data 26 octombrie 2013 18:35:48
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <deque>

using namespace std;

typedef struct elem{
    int pos;
    int value;
} ELEM;

int n,k;

deque<ELEM> elements;

void addElem(int pos, int value){
    ELEM elem;
    elem.pos = pos;
    elem.value = value;

    while (elements.size() != 0 && elements.back().value >= value){
        elements.pop_back();
    }

    elements.push_back(elem);
}

void eliminateFromFront(int pos){

    while (elements.front().pos < pos){
        elements.pop_front();
    }
}

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

    scanf("%d %d", &n, &k);

    int result = 0;

    int elem;
    for (int i=1; i<=k; i++){
        scanf("%d", &elem);
        addElem(i, elem);
    }

    result += elements.front().value;
    for (int i=k+1; i<=n; i++){
        eliminateFromFront(i-k+1);

        scanf("%d", &elem);
        addElem(i, elem);

        result += elements.front().value;
    }

    printf("%d", result);

    return 0;
}