Cod sursa(job #1556218)

Utilizator Corneliu10Dumitru Corneliu Corneliu10 Data 24 decembrie 2015 13:11:31
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <cstdio>
#include <deque>
using namespace std;

deque <int> minim;
int v[5000010];

int main()
{
    int i,n,k;
    long long sm = 0;
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);

    scanf("%d%d",&n,&k);

    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);

    minim.push_back(1);
    for(i=2;i<=n;i++)
    {
        while(!minim.empty() && v[i] < v[minim.back()]) minim.pop_back();

        minim.push_back(i);

        if(minim.front() == i - k) minim.pop_front();

        if(i >= k) sm += v[minim.front()];
    }

    printf("%d",sm);
}