Cod sursa(job #2456997)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 16 septembrie 2019 10:51:12
Problema Deque Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <deque>
#include <limits.h>
using namespace std;
ifstream cin("deque.in");
ofstream cout("deque.out");
deque< pair<int,int> > q;
int a,n,k,suma;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin>>n>>k;
    cin>>a;
    q.push_back(make_pair(a,1));
    for(int i=2;i<=k;++i)
    {
        cin>>a;
        while(a<=q.front().first)
        {
            q.pop_front();
        }
        q.push_back(make_pair(a,i));
    }
    suma+=q.front().first;
    for(int i=k+1;i<=n;++i)
    {
        cin>>a;
        while((a<=q.front().first||q.front().second<=i-k)&&q.size()) q.pop_front();
        q.push_back(make_pair(a,i));
        suma+=q.front().first;
    }
    cout<<suma<<"\n";
    return 0;
}