Cod sursa(job #2033645)

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

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

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

int main()
{
    int 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;
}