Cod sursa(job #2159408)

Utilizator EclipseTepes Alexandru Eclipse Data 10 martie 2018 22:09:20
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

unsigned int n, k;
long long int S;

struct Element {
    int value;
    int index;
} temp;

deque<Element> myDeque;

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

int main()
{
    unsigned int i, j;
    fin >> n >> k;
    for (i = 1; i <= n; i++) {
        fin >> temp.value;
        temp.index = i;
        if (myDeque.empty()) myDeque.push_back(temp);
        else {
            if (temp.value < myDeque.front().value) {
                myDeque.push_front(temp);
            } else {
                while (myDeque.back().value > temp.value) {
                    myDeque.pop_back();
                }
                myDeque.push_back(temp);
            }
        }

        while (myDeque.front().index + k <= i) myDeque.pop_front();
        if (i >= k) /*cout << myDeque.front().value << '\n';*/ S += myDeque.front().value;
    }
    fout << S;
    return 0;
}