Cod sursa(job #310028)

Utilizator sandyxpSanduleac Dan sandyxp Data 1 mai 2009 17:02:42
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <iterator>
#include <queue>
using namespace std;

#define NUME "deque"
ifstream fi(NUME".in");
ofstream fo(NUME".out");

deque<int> Q, elem;

int main()
{
    int N, K, x;
    long long calc = 0;
    fi >> N >> K;
    for (int i = 0; i < N; ++i) {
        fi >> x;
        if (i >= K)
            elem.pop_back();
        elem.push_front(x);

        while (!Q.empty() && x < elem[i-Q.back()])
            Q.pop_back();
        Q.push_back(i);
        while (!Q.empty() && i - Q.front() >= K)
            Q.pop_front();
       /* 
        for (int j = 0; j < Q.size(); ++j)
            fo << elem[i-Q[j]] << " ";
        fo << "\n";
        */
        if (i >= K-1)
            calc += elem[i-Q.front()]; // minimul
    }
    fo << calc << endl;
    return 0;
}