Cod sursa(job #1075789)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 9 ianuarie 2014 16:17:25
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include <cstdio>

using namespace std;
int i,a[5000003],n,k,b[5000003],Min,j,u,p;

void pune(int i)
{
  while(u>=p && a[b[u]]>a[i])
  --u;
  ++u;
  b[u]=i;
}

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

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

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

    p=1;u=0;

    for(i=1;i<k;++i)
    pune(i);

    Min=0;

    for(i=k;i<=n;++i)
    {
      pune(i);
      Min+=a[b[p]];
      if(i-b[p]==k-1) p++;

    }

     printf("%d\n",Min);





    return 0;
}