Cod sursa(job #1628116)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 3 martie 2016 21:11:33
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
#include <vector>
#include <deque>
#define INF 0x3f3f3f3f
using namespace std;

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

using VI = vector<int>;
using VVI = vector<VI>;

int n, k, s;
VI a;
deque<int> q;

int main()
{
    is >> n >> k;
    a = VI(n + 1);
    for ( int i = 1; i <= n; ++i )
    {
        is >> a[i];
        while ( q.size() && a[i] <= a[q.back()] )
            q.pop_back();
        q.push_back(i);
        if ( i < k )
            continue;
        if ( i - q.front() >= k )
            q.pop_front();
        s += a[q.front()];
    }
    os << s;
    is.close();
    os.close();
    return 0;
}