Cod sursa(job #1046733)

Utilizator PsychoAlexAlexandru Buicescu PsychoAlex Data 3 decembrie 2013 13:45:17
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <deque>

std::ifstream fin("deque.in");
std::ofstream fout("deque.out");

int n, siz;
struct nod
{
    int indice, val;
};

void citire()
{
    std::deque<nod> moFoList;
    fin>>n>>siz;

    long long suma = 0;
    int p;
    for(int i = 0; i < n; i++)
    {
        fin>>p;
        if(moFoList.front().indice < i - siz + 1)
        {
            moFoList.pop_front();
        }
        while(moFoList.size() && moFoList.back().val > p)
        {
            moFoList.pop_back();
        }

        nod elem;
        elem.indice = i;
        elem.val = p;
        moFoList.push_back(elem);

        if(i >= siz - 1)
        {
            suma += moFoList.front().val;
        }
    }
    fout<<suma<<'\n';
}

int main()
{
    citire();
    return 0;
}