Pagini recente » Borderou de evaluare (job #2568372) | Cod sursa (job #1929008)
#include <iostream>
#include <cstdio>
#include <deque>
using namespace std;
int v[5000002];
deque < pair < int , int > > q;
int main()
{
freopen("deque.in", "r", stdin);
freopen("deque.out", "w", stdout);
int n,k;
long long sol=0;
scanf("%d %d", &n, &k);
for(int i=1;i<=n;i++)
scanf("%d", &v[i]);
for(int i=1;i<=k-1;i++)
{
int x=v[i];
while(!q.empty() && q.back().first>=x)
q.pop_back();
q.push_back(make_pair(x,i));
}
for(int i=k;i<=n;i++)
{
int x=v[i];
while(!q.empty() && q.back().first>=x)
q.pop_back();
if(!q.empty() && q.front().second<=i-k)
q.pop_front();
q.push_back(make_pair(x,i));
long long val=q.front().first;
sol+=val;
}
printf("%I64d\n", sol);
fclose(stdin);
fclose(stdout);
return 0;
}