Pagini recente » Cod sursa (job #473546) | Cod sursa (job #1138646) | Cod sursa (job #552249) | Cod sursa (job #1613325) | Cod sursa (job #2208461)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("deque.in");
ofstream fout ("deque.out");
int v[5000005];
deque <int> D;
void inserare (int i)
{
if (D.empty()) D.push_back(i);
else {
while (D.size() && v[D.back()] >= v[i]) D.pop_back();
D.push_back(i);
}
}
int main()
{
int n, k;
fin >> n >> k;
for (int i = 1; i <= n; i ++) fin >> v[i];
int suma = 0;
for (int i = 1; i <= k; i ++) inserare(i);
suma += v[D.front()], D.pop_front();
for (int i = k + 1; i <= n; i ++) {
inserare(i);
suma += v[D.front()];
if (D.front() + k - 1 <= i) D.pop_front();
}
fout << suma;
fin.close();
fout.close();
return 0;
}