Pagini recente » Cod sursa (job #85819) | Cod sursa (job #915856) | Cod sursa (job #1153261) | Cod sursa (job #247643) | Cod sursa (job #1804112)
#include <iostream>
#include <cstdio>
#include <deque>
using namespace std;
int n,k;
int a[5000004];
int p;
int s;
deque <int> dq;
void calc(int poz)
{
while(a[dq.back()]>a[poz])
dq.pop_back();
dq.push_back(poz);
if(dq.back()-k+1>dq.front())
dq.pop_front();
s+=a[dq.front()];
}
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
scanf("%d %d", &n, &k);
for(int i=0;i<n;i++)
scanf("\n%d", &a[i]);
dq.push_front(0);
for(int i=1;i<k-1;i++)
{
while(a[dq.back()]>a[i])
dq.pop_back();
dq.push_back(i);
}
for(int i=k-1;i<n;i++)
{
calc(i);
}
printf("%d",s);
return 0;
}