Pagini recente » Cod sursa (job #2403748) | Cod sursa (job #1456328) | Cod sursa (job #2507026) | Cod sursa (job #311078) | Cod sursa (job #546276)
Cod sursa(job #546276)
/*
Elem noi sterg din coada de la sfarsit cele mai mari ca ea.
(sunt preferate elem minime de indice mai mare)
*/
#include <cstdio>
#include <deque>
using namespace std;
const int N = 5000001;
deque<int> coada;
int v[N];
int n,k;
void citire()
{
scanf("%i%i",&n,&k);
for (int i = 1; i <= n; ++i)
scanf("%i",&v[i]);
}
void rezolvare_deque()
{
int s=0;
for (int i = 1; i <= n; ++i)
{
while ((coada.size() > 0)&&(v[coada.back()] >= v[i]))
coada.pop_back();
if ((coada.size() > 0)&&(i-coada.front()+1 > k))
coada.pop_front();
coada.push_back(i);
if (i >= k)
s += v[coada.front()];
}
printf("%i",s);
}
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
citire();
rezolvare_deque();
return 0;
}