Pagini recente » Cod sursa (job #1528950) | Cod sursa (job #2125790) | Cod sursa (job #2797867) | Cod sursa (job #2769702) | Cod sursa (job #2181141)
#include <iostream>
#include <fstream>
#include <deque>
#define lim 5000000
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
int a[lim];
deque <int> dq;
int main()
{
int n,k;
long long s=0;
fin>>n>>k;
for(int i=0;i<n;i++)
fin>>a[i];
dq.push_front(0);
for(int i=1;i<n;i++)
{
while(!dq.empty() && a[dq.back()]>a[i])
dq.pop_back();
dq.push_back(i);
if(dq.front()+k<=i)
{
dq.pop_front();
}
if(i>=k-1)s+=a[dq.front()];
}
fout<<s;
return 0;
}