Cod sursa(job #1277116)

Utilizator FeriCsiki Francisc Alexandru Feri Data 27 noiembrie 2014 09:48:56
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int st,dr,d[5000001],k,n,v[5000001];

void stanga(int i)
{
    if(i-d[st]==k)
        st++;
}

void dreapta(int i)
{
    while(st<=dr && v[i]<=v[d[dr]])
    {
        dr--;
    }
    d[++dr]=i;

}

int main()
{
    int i;
    long long smin=0;

    in>>n>>k;

    for(i=1;i<=n;i++)
    {
        in>>v[i];
    }
    //st=1;
    //dr=k+1;
    for(i=1;i<=n;i++)
    {
        dreapta(i);
        stanga(i);
        //out<< v[d[st]]<<" ";
        if(i>=k)
            smin+=v[d[st]];
    }
    out<<smax;
    return 0;
}