Pagini recente » Cod sursa (job #1356031) | Cod sursa (job #2822914) | Cod sursa (job #2987331) | Cod sursa (job #1455046) | Cod sursa (job #2646875)
#include <deque>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
int main()
{
int n, k, s = 0;
fin >> n >> k;
deque<int> d;
vector<int> v(n + 1);
for (int i = 1; i <= n; ++i)
fin >> v[i];
d.push_back(1);
for (int i = 2; i <= k; ++i)
{
while (!d.empty() and v[d.back()] >= v[i])
{
d.pop_back();
}
d.push_back(i);
}
s += v[d.front()];
for (int i = k + 1; i <= n; ++i)
{
while (!d.empty() and v[d.back()] >= v[i])
{
d.pop_back();
}
d.push_back(i);
if (d.front() <= i - k)
d.pop_front();
s += v[d.front()];
}
fout << s;
}