Cod sursa(job #2724099)

Utilizator AACthAirinei Andrei Cristian AACth Data 16 martie 2021 14:33:40
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
const int Max = 1e5 + 1;
void nos()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
int n,k;
void read()
{
    f>>n>>k;
}
struct entry{
    int indice;
    int val;
};
void solve()
{
    deque < entry > c;
    long long  sum = 0;
    int i;
    for(i=1;i<=k;i++)
    {
        entry this_entry;
        f>>this_entry.val;
        this_entry.indice = i;
        while(!c.empty() and c.back().val > this_entry.val)
            c.pop_back();
        c.push_back(this_entry);
    }
    for( i = k+1 ; i <= n;i++)
    {
        sum += c.front().val;
        entry this_entry;
        f>>this_entry.val;
        this_entry.indice = i;
        while(!c.empty() and c.back().val > this_entry.val)
            c.pop_back();
        c.push_back(this_entry);
        while(!c.empty() and this_entry.indice - c.front().indice >= k)
            c.pop_front();
    }
    sum+=c.front().val;
    g<<sum;
}
void restart()
{

}

int32_t main()
{

        read();
        solve();
        restart();
    return 0;
}