Pagini recente » Cod sursa (job #1426040) | Cod sursa (job #2496192) | Cod sursa (job #22740) | Cod sursa (job #491156) | Cod sursa (job #2040960)
/// Inspirat, un pic, dupa sursa oficiala :)
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
int main()
{
const int N = 5000;
long long sum_of_all_minimal_values = 0;
int n,k,front,back;
int deque[N], values[N];
in>>n>>k;
front = 1;
back = 0;
for(int index = 1; index <= n; ++index) in>>values[index];
for(int index = 1; index <= n; ++index)
{
int crt_value = values[index];
while(front <= back && crt_value < values[deque[back]]) /// Remove all smaller elements
--back;
deque[++back] = index;
while(front <= back && (index - deque[front] + 1) > k) /// Remove elements outside the current sequence's range = K
++front;
if(index >= k)
sum_of_all_minimal_values += values[deque[front]];
//for(int i=front; i<=back; ++i) cout<<values[deque[i]]<<" "; cout<<"\n";
}
out<<sum_of_all_minimal_values;
return 0;
}