Pagini recente » W | Borderou de evaluare (job #2538232) | Cod sursa (job #2618114)
#include<bits/stdc++.h>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
deque<pair<int,int>>coada;
int n,k,i;
int v[5000001];
long long sumaMin;
int main()
{
f>>n>>k;
deque<pair<int,int>>coada;
for(i = 1; i <= n; i++)
f>>v[i];
coada.push_back({v[1], 1});
for(i = 2; i <= k; i++)
{
while(coada.back().first >= v[i])
if(coada.size() != 0)
coada.pop_back();
else break;
coada.push_back({v[i], i});
}
sumaMin = coada.front().first;
for(i = k+1; i <= n; i++)
{
while(coada.back().first >= v[i])
if(coada.size() != 0)
coada.pop_back();
else break;
coada.push_back({v[i], i});
if(coada.front().second == i-k)
coada.pop_front();
sumaMin += coada.front().first;
}
g<<sumaMin;
return 0;
}