Cod sursa(job #2179796)

Utilizator tudortarniceruTudor Tarniceru tudortarniceru Data 20 martie 2018 14:13:10
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;

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

int n, s;
long long sol;
deque< pair<int, int> > q;

int main() {

    fin >> n >> s;
    for (int i = 1; i <= n; ++i) {
        long long k;
        fin >> k;
        while (!q.empty() && q.back().first >= k) {
            q.pop_back();
        }
        q.push_back(make_pair(k, i));
        if (i >= s) {
            while(!q.empty() && q.front().second < i - s + 1) {
                q.pop_front();
            }
            sol += q.front().first;
        }
    }

    fout << sol;

    fout.close();
    return 0;
}