Cod sursa(job #2173218)

Utilizator markyDaniel marky Data 15 martie 2018 21:09:21
Problema Deque Scor 100
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.empty() && (q.back().first >= x || q.back().second < (i-k+1)))
        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.empty() && (q.back().first >= x || q.back().second < (i-k+1)))
        q.pop_back();

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

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

    g<<suma<<'\n';

    return 0;
}