Cod sursa(job #1277071)

Utilizator cristinamateiCristina Matei cristinamatei Data 27 noiembrie 2014 09:15:21
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
#include<iostream>

using namespace std;

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

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

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

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

int main()
{
    int i, s = 0;
    in >> n >> k;
    for ( i = 1; i <= n; i++ )
        in >> v[i];
    for ( i = 1; i <= n; i++ )
    {
        stanga(i);
        dreapta(i);
        if ( i >= k && i <= n - k + 1 )
            s+= v[dq[st]];
    }
    out << s;
    return 0;
}