Cod sursa(job #1994559)

Utilizator racheriunicolaechowchow racheriunicolae Data 25 iunie 2017 12:53:27
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.45 kb
#include <fstream>
#include <deque>
using namespace std;
long long sum;
int a[5000005],n,i,k,x[5000005];
int f,b;

int main()
{
    ifstream fin("deque.in");
    ofstream fout("deque.out");
    fin>>n>>k;
    for(i=1;i<=n;i++)
        fin>>a[i];
f=1;b=0;
    for(i=1;i<=n;i++)
    {
        while(f<=b and a[i]<= a[ x[b] ])b--;
        x[++b]=i;
        if(x[f]==i-k)f++;
        if(i>=k)sum+=a[x[f]];
    }
    fout<<sum;
    return 0;
}