Cod sursa(job #1923299)

Utilizator radu_uniculeu sunt radu radu_unicul Data 10 martie 2017 22:09:45
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<stdio.h>
using namespace std;

int n,k;
int   v[5000005];
int deq[5000005];
int front,back;

void printdeq()
{
    for(int i=front;i<=back;i++) printf("DEQ:%d NUMBER:%d ",deq[i],v[deq[i]]);
    printf("\n");
    //printf("%d\n",v[deq[back]]);
}

int main()
{
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);

    long long sum=0;

    scanf("%d %d",&n,&k);
    front=1;back=0;

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

    for(int i=1;i<=n;i++)
    {
        while(front<=back&&v[deq[back]]>=v[i]) back--;
        deq[++back]=i;
        if(deq[front]==i-k) front++;
        //printdeq();
        if(i>=k) sum+=v[deq[front]];
    }
    printf("%d",sum);
}