Cod sursa(job #2044274)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 21 octombrie 2017 09:09:07
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <fstream>
#include <deque>

using namespace std;

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

deque <int> d;

int a[5000000];
int n,k;
long long SUM;

void Read()
{
   fin>>n>>k;
   for(int i=1; i<=n; ++i)
      fin>>a[i];

   fin.close();
}

void Do()
{
  for(int i=1; i<=n; ++i)
  {
    while(!d.empty() && a[i]<=a[d.back()])
     d.pop_back();

    d.push_back(i);

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

    if(i>=k) SUM+=a[d.front()];
  }

  //fout<<a[i]<<' ';
}

void Print()
{
   fout<<SUM<<'\n';
   fout.close();
}

int main()
{
   Read();
   Do();
   Print();

    return 0;
}