Cod sursa(job #1976996)

Utilizator blatulInstitutul de Arta Gastronomica blatul Data 4 mai 2017 19:25:26
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <bits/stdc++.h>
using namespace std;

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

deque< pair<int, int> > dq;

int main() {

    int N, K;

    fin >> N >> K;

    long long sum = 0;

    int x;
    for (int i = 1; i <= N; ++i) {

        fin >> x;

        while (!dq.empty() && x <= dq.back().first)
            dq.pop_back();

        dq.push_back(make_pair(x, i));

        if (i - dq.front().second >= K)
            dq.pop_front();

        if (i >= K)
            sum += dq.front().first;
    }

    fout << sum;

    return 0;
}