Pagini recente » Cod sursa (job #1419867) | Cod sursa (job #661326) | Cod sursa (job #3213909) | Cod sursa (job #777643) | Cod sursa (job #3242736)
#include <iostream>
#include <fstream>
#include <deque>
#include <vector>
using namespace std;
int main() {
ifstream fin("deque.in");
ofstream fout("deque.out");
deque<pair<int, int>> coada;
int suma=0, N, K, i;
fin >> N >> K;
vector<int> a(N+1);
for(int i=1; i<=N; ++i) {
fin >> a[i];
}
for(int i=1; i<=K; ++i) {
while(!coada.empty() && coada.back().first >= a[i]) {
coada.pop_back(); // ștergem elementele mai mari -- întotdeauna cel din spate este maxim
}
coada.push_back({a[i], i});
}
suma += coada.front().first; // minimul
for(i=K+1; i<=N; ++i) {
while(!coada.empty() && coada.back().first >= a[i]) {
coada.pop_back(); // ștergem elementele mari
}
coada.push_back({a[i], i});
while(!coada.empty() && coada.front().second <= i-K) {
coada.pop_front(); // ștergem elementele vechi
}
suma += coada.front().first;
}
fout << suma;
}