Cod sursa(job #905866)

Utilizator SPDionisSpinei Dionis SPDionis Data 6 martie 2013 11:38:19
Problema Deque Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <deque>

using std::deque;
std::ifstream in("deque.in");
std::ofstream out("deque.out");

deque<long> a;
long N,K;

long mm()
{
    long t = a[0];
    for (int i = 1; i < a.size(); ++i)
        if ( a[i] < t ) t = a[i];
    return t;
}


int main()
{
    in >> N >> K;
    long long suma = 0;
    long long minim = 2e10;
    for (int i = 0; i < K; ++i) {
        long t; in >> t;
        a.push_back(t);
        if ( t < minim ) minim = t;
    }

    suma += minim;

    for (long i = K; i < N; ++i) {
        long t; in >> t;
        a.push_back(t);
        if ( minim == a.front() ) { a.pop_front(); minim = mm(); }
        else { if ( t < minim ) minim = t; a.pop_front(); }
        suma += minim;
    }


    out << suma;

    in.close();
    out.close();
    return 0;
}