Cod sursa(job #1880141)

Utilizator tudoras8tudoras8 tudoras8 Data 15 februarie 2017 15:58:54
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int n, k;
long long ans;
vector<long long> v;

int main(int argc, const char * argv[]) {
    ifstream cin("deque.in");
    ofstream cout("deque.out");
    
    cin >> n >> k;
    v.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    
    deque<pair<long long, int>> candidates;
    
    for (int i = 0; i < n; i++) {
        while (!candidates.empty() && v[i] < candidates.back().first) {
            candidates.pop_back();
        }
        candidates.push_back(make_pair(v[i], 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;
}