Cod sursa(job #1880137)

Utilizator tudoras8tudoras8 tudoras8 Data 15 februarie 2017 15:47:25
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 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 < k; i++) {
        candidates.push_back(make_pair(v[i], i));
    }
    
    sort(candidates.begin(), candidates.end());
    ans += candidates.front().first;
    
    for (int i = k; 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();
        }
        
        long long minVal = candidates.front().first;
        ans += minVal;
    }
    
    cout << ans;
    
    return 0;
}