Cod sursa(job #2033654)

Utilizator radudurlesteanuDurlesteanu Radu Stefan radudurlesteanu Data 7 octombrie 2017 09:42:11
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>
#include <deque>
using namespace std;

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

deque <long> q;
long a[5000003],n,k;

int main()
{
    long long x,s,i;

    fin>>n>>k;
    for (i=1;i<=n;++i) fin>>a[i];

    for (i=1;i<=k;++i)
    {
        x=a[i];
        while (!q.empty() && x<=a[q.back()]) q.pop_back();
        q.push_back(i);
    }
    s=a[q.front()];

    for (i=k+1;i<=n;++i)
    {
        x=a[i];
        while (!q.empty() && x<=a[q.back()]) q.pop_back();
        q.push_back(i);

        if (i-q.front()>=k) q.pop_front();
        s+=a[q.front()];
    }

    fout<<s;
    return 0;
}