Cod sursa(job #2541666)

Utilizator Galatanu_BogdanGalatanu Bogdan Ioan Galatanu_Bogdan Data 8 februarie 2020 18:13:54
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <deque>
#include <vector>
using namespace std;
ifstream cin("deque.in");
ofstream cout("deque.out");
deque<int>coada;
vector<int>a;
int n,k,sum = 0;
void citire()
{
    cin>>n>>k;
    a.push_back(0);
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        a.push_back(x);
    }
        }

int main()
{
    citire();
    coada.push_back(1);
    for(int i=1;i<=n;i++)
    {
        while(!coada.empty() && a[i] <= a[coada.back()])
            coada.pop_back();
        
        coada.push_back(i);
        
        if(coada.front() == i-k)
            coada.pop_front();
        
        if(i >= k)
            sum += a[coada.front()];
        
        }
    cout<<sum<<'\n';
}