Cod sursa(job #1112246)

Utilizator DanielRusuDaniel Rusu DanielRusu Data 19 februarie 2014 16:50:05
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <deque>

using namespace std;

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

struct numar {
    int val, poz;
};

numar x;
int i, n, k, nr, s;

int main() {
    deque<numar> mydeque;

    fin >> n >> k;

    for(i = 1;i <= n;i++) {
        fin >> nr;

        while(!mydeque.empty() && mydeque.front().poz < i - k + 1) {
            mydeque.pop_front();
        }

        while(!mydeque.empty() && mydeque.back().val > nr) {
            mydeque.pop_back();
        }

        x.val = nr;
        x.poz = i;

        mydeque.push_back(x);

        if(i >= k) s += mydeque.front().val;
    }

    fout << s << '\n';

    fin.close();
    fout.close();

    return 0;
}