Cod sursa(job #943839)

Utilizator PetrutiuPaulPetrutiu Paul Gabriel PetrutiuPaul Data 26 aprilie 2013 16:04:06
Problema Deque Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <iostream>
#include <fstream>

#define inf 9999999

using namespace std;

      ifstream fin("deque.in");
      ofstream fout("deque.out");

int a[10000],b[100000];
int st=1,dr,k;

void stanga(int i)
{
      while(i-b[st]==k)st++;
}
void dreapta(int i)
{
      while(st<=dr && a[i]<=a[b[dr]])
      dr--;
}
int main()
{
    long long i,j,n,m,k,mi=inf,s=0;
    fin>>n>>k;
    for(i=1;i<=n;i++)
    fin>>a[i];
    for(i=1;i<=n;i++)
    {
          if(i>k)stanga(i);
          dreapta(i);
          b[++dr]=i;
          if(i>=k)s+=a[b[st]];
    }
    fout<<s;
}