Cod sursa(job #1880142)

Utilizator tudoras8tudoras8 tudoras8 Data 15 februarie 2017 16:00:27
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int n, k;
long long ans;

int main(int argc, const char * argv[]) {
    ifstream cin("deque.in");
    ofstream cout("deque.out");
    
    cin >> n >> k;
    
    deque<pair<long long, int>> candidates;
    
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        
        while (!candidates.empty() && x < candidates.back().first) {
            candidates.pop_back();
        }
        candidates.push_back(make_pair(x, i));
        
        while (!candidates.empty() && candidates.front().second < i - k + 1) {
            candidates.pop_front();
        }
        
        if (i + 1 >= k) {
            long long minVal = candidates.front().first;
            ans += minVal;
        }
    }
    
    cout << ans;
    
    return 0;
}