Pagini recente » Cod sursa (job #276713) | Cod sursa (job #2305841) | Cod sursa (job #2606474) | Cod sursa (job #363475) | Cod sursa (job #2614770)
#include <bits/stdc++.h>
std::ifstream fin("deque.in");
std::ofstream fout("deque.out");
int n, k;
int deque[5000001], v[5000001];
void push_back(int deque[], int val, int &back)
{
deque[++back] = val;
}
void pop_back(int deque[], int &back)
{
back--;
}
void pop_front(int deque[], int val, int &front)
{
front++;
}
int main()
{
int i, back = -1, front = 0;
long long mins = 0;
fin >> n >> k;
for(i = 0; i < n; i++)
fin >> v[i];
push_back(deque, 0, back); // 0
for(i = 1; i < n; i++)
{
while(v[i] <= v[deque[back]] && front <= back)
pop_back(deque, back);
push_back(deque, i, back);
if(i >= k - 1)
{
mins += v[deque[front]];
//std::cout<< "Min: " << v[deque[front]] <<'\n';
}
if(i - k + 1 == deque[front])
pop_front(deque, i, front);
}
fout << mins;
return 0;
}