Pagini recente » Cod sursa (job #87786) | Cod sursa (job #3189437) | Cod sursa (job #2524887) | Cod sursa (job #917505) | Cod sursa (job #3174654)
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
ifstream fin ("deque.in");
ofstream fout ("deque.out");
int main () {
int n, k, sum = 0;
fin >> n >> k;
vector <int> v(n);
deque <int> dq;
for (int i = 0; i < n ; i++) {
fin >> v[i];
//dq.front == stanga
//dq.back == dreapta
if(!dq.empty() && dq.front() == i - k ){
// daca elementul din stanga iese din parametrii dati, il stergem
dq.pop_front();
}
//eliminam elemente daca oricum nu mai pot fi minime, de ex 8 1 7 => 1
while(!dq.empty() && v[i] <= v[dq.back()]) {
dq.pop_back();
}
dq.push_back(i);
if(i >= k - 1) {
// daca deque-ul este destul de lung
sum += v[dq.front()];
}
}
fout << sum;
}