Cod sursa(job #533747)

Utilizator feelshiftFeelshift feelshift Data 14 februarie 2011 16:00:43
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
// http://infoarena.ro/problema/deque
#include <fstream>
#include <vector>
#include <deque>
using namespace std;

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

vector<int> number;
deque<int> myQueue;

int main() {
    int nrNumbers;  // cate numere sunt in fisierul de intrare
    int lenght; // lungimea subsecventei
    int sum = 0;
    int tmp;

    in >> nrNumbers >> lenght;
    number.push_back(0);

    for(int i=1;i<=nrNumbers;i++) {
        in >> tmp;

        number.push_back(tmp);
    }

    for(int currentPosition=1;currentPosition<=nrNumbers;currentPosition++) {
        while(!myQueue.empty() && myQueue.front() <= myQueue.back() && number[currentPosition] <= number[myQueue.back()])
            myQueue.pop_back();

        myQueue.push_back(currentPosition);

        if(myQueue.front() == currentPosition - lenght)
            myQueue.pop_front();

        if(currentPosition >= lenght)
            sum = sum + number[myQueue.front()];
    }

    out << sum << "\n";

    return (0);
}