Pagini recente » Cod sursa (job #611290) | Cod sursa (job #156599) | Cod sursa (job #2500981) | Cod sursa (job #1557110) | Cod sursa (job #2842334)
#include <iostream>
#include <vector>
#include <deque>
#include <fstream>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
int main()
{
int n, k, sum = 0, nr = 0, c = 1, cop;
in>> n >> k;
vector<int> v(n);
for (int i = 0; i < n; i++)
in>> v[i];
deque<int> dQ;
dQ.push_front(v[0]);
nr++;
cop = dQ.front();
if (nr == k)
{
sum += dQ.back();
if (c == k)
dQ.pop_back();
nr--;
}
for (int i = 1; i < n; i++)
{
nr++;
if (dQ.empty() || v[i] > dQ.front())
dQ.push_front(v[i]);
else
{
while (not dQ.empty() && v[i] <= dQ.front())
{
dQ.pop_front();
}
dQ.push_front(v[i]);
}
if (cop == dQ.back())
c++;
else
{
cop = dQ.back();
c = 1;
}
if (nr == k)
{
sum += dQ.back();
if (c == k)
{
dQ.pop_back();
c = 0;
if (i < n - 1)
cop = v[i + 1];
}
nr--;
}
}
out<< sum;
in.close();
out.close();
return 0;
}