Cod sursa(job #1046721)

Utilizator PsychoAlexAlexandru Buicescu PsychoAlex Data 3 decembrie 2013 13:36:00
Problema Deque Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 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;

    int suma = 0;
    int lastMinim = 10000001;
    if(n >= siz)
    {
        int p;
//        for(int i = 0; i < siz; i++)
//        {
//            fin>>p;
//            if(p < lastMinim)
//            {
//                lastMinim = p;
//            }
//            moFoList.push_back(p);
//        }
//        fin>>p;
//        nod sss;
//        sss.indice = 0;
//        sss.val = p;
//        moFoList.push_back(sss);
        for(int i = 0; i < n; i++)
        {
            fin>>p;
            nod sss2;
            sss2.indice = i;
            sss2.val = p;

            if(moFoList.size() && i >= siz - 1)
            {
                if(moFoList.front().indice < i - siz + 1)
                {
                    moFoList.pop_front();
                }
                if(moFoList.front().val > p)
                {
                    moFoList.pop_front();
                }
                    while(moFoList.size() && moFoList.back().val > p)
                    {
                        moFoList.pop_back();
                    }
                    moFoList.push_back(sss2);
//                }
            }
            else
            {
                moFoList.push_back(sss2);
            }
            if(i >= siz - 1)
            {
                suma += moFoList.front().val;
//                std::cout<<i + 1<<": "<<moFoList.front().val<<'\n';
            }
        }
    }
    fout<<suma<<'\n';
}

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