Cod sursa(job #1804130)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 12 noiembrie 2016 11:34:14
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <cstdio>
#include <deque>

using namespace std;
int n,k;
int a[5000005];
int p;
int s;
deque <int> dq;
void calc(int poz)
{
    while(!dq.empty() && a[dq.back()]>a[poz])
            dq.pop_back();
    dq.push_back(poz);
    if(dq.back()-k+1>dq.front())
        dq.pop_front();
    s+=a[dq.front()];
}
int main()
{
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);
    scanf("%d %d", &n, &k);
    for(int i=0;i<n;i++)
        scanf("\n%d", &a[i]);
    dq.push_back(0);
    for(int i=1;i<k-1;i++)
    {
        while(!dq.empty() && a[dq.back()]>a[i])
            dq.pop_back();
        dq.push_back(i);
    }
    for(int i=k-1;i<n;i++)
    {
        calc(i);
    }
    printf("%d",s);
    return 0;
}