Cod sursa(job #1254145)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 2 noiembrie 2014 11:42:00
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<fstream>
#define NMAX 5000010

using namespace std;

ifstream f("deque.in");
ofstream g("deque.out");

int n, k, p, u, a[NMAX], dq[NMAX];
long long sumaMinime=0;

void adaugaSpate(int valoare, int pozitie)
{
    while (a[dq[u]]>valoare && u>=p) --u;
    dq[++u]=pozitie;
}

void eliminaFata(int pozitie)
{
    if (pozitie-dq[p]==k) ++p;
}

int main()
{
    f>>n>>k>>a[1];

    p=u=1; dq[p]=1;
    for (int i=2; i<=n; ++i)
    {
        f>>a[i];

        eliminaFata(i);

        adaugaSpate(a[i], i);

        if (i>=k) sumaMinime+=a[dq[p]];
    }

    g<<sumaMinime<<"\n";

    return 0;
}