Cod sursa(job #1923233)

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

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

void printdeq()
{
    for(int i=back;i<=front;i++) printf("%d ",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=-1;
    for(int i=0;i<k;i++)
    {
        scanf("%d",&v[i]);
        deq[++front]=i;
        while(front>back && v[deq[front-1]]>=v[deq[front]])
        {
            deq[front-1]=deq[front];
            front--;
        }
    }
    sum+=v[deq[back]];

    for(int i=k;i<n;i++)
    {

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