Cod sursa(job #2677293)

Utilizator cyg_dragos10Ivan Dragos cyg_dragos10 Data 26 noiembrie 2020 10:14:44
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream fin("deque.in");
ofstream fout("deque.out");

struct PAIR
{
    int first,last;
};
deque <PAIR> deq;

int main()
{
    int n,nr,i,k;
    long long ans =0;
    fin>>n>>k;
    for(i = 1;i <= n;i++)
    {
        fin>>nr;
        while(!deq.empty() && deq.back().first > nr)
        {
            deq.pop_back();
        }
        PAIR x;
        x.first = nr;
        x.last = i;
        deq.push_back(x);
        if(deq.front().last<=i-k)
        {
            deq.pop_front();
        }
        if(i>=k)
        {
            ans+=deq.front().first;
        }
    }
    fout<<ans;
    return 0;
}