Cod sursa(job #1650855)

Utilizator Vali_DeaconuVali Deaconu Vali_Deaconu Data 11 martie 2016 21:01:31
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
# include <fstream>
# include <deque>

using namespace std;

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

deque< pair<int, int> > d;
int n, x, i, k;
long long sum;

int main() {
    fin >> n >> k;
    for (i=1; i<k; ++i) {
        fin >> x;
        while (!d.empty() && d.back().first > x)
            d.pop_back();

        d.push_back(make_pair(x, i));
    }

    for (i=k; i<=n; ++i) {
        fin >> x;

        if (i - d.front().second >= k)
            d.pop_front();

        while (!d.empty() && d.back().first > x)
            d.pop_back();

        d.push_back(make_pair(x, i));
        sum += d.front().first;
    }

    fout << sum;
    return 0;
}