Cod sursa(job #2173130)

Utilizator markyDaniel marky Data 15 martie 2018 20:51:40
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <deque>

using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");

deque<pair<int,int> >q;

int main()
{


    int n,k,x;
    f>>n>>k;
    f>>x;
    q.push_back(make_pair(x,1));
    for(int i=2;i<=k-1;++i){
            f>>x;
        while((q.back().first >= x || q.back().second < (i-k+1)) && !q.empty())
        q.pop_back();

    q.push_back(make_pair(x,i));
    }
    long long suma = 0;
    for(int i=k;i<=n;++i){
            f>>x;
        while((q.back().first >= x || q.back().second < (i-k+1)) && !q.empty())
        q.pop_back();

    q.push_back(make_pair(x,i));
    while(q.front().second < (i-k+1) && !q.empty())
        q.pop_front();

    suma += q.front().first;
    }

    g<<suma<<'\n';

    return 0;
}