Pagini recente » Cod sursa (job #566649) | Cod sursa (job #2279100) | Cod sursa (job #1494562) | Cod sursa (job #618368) | Cod sursa (job #2719935)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
int v[5000000];
deque <int> pos;
int main()
{
long long sum;
int n, k, i, x;
in>>n>>k;
sum = 0;
for( i = 1; i <= n; i++ ){
in>>v[i];
}
sum = 0;
for( i = 1; i <= n; i++ ){
while( pos.size() > 0 && v[pos.back()] >= v[i] )
pos.pop_back();
pos.push_back(i);
if( pos.front() == i - k){
//out<<v[pos.front()]<<" "<<pos.size()<<'\n';
pos.pop_front();
}
if( i >= k )
sum+=v[pos.front()];
}
out<<sum;
return 0;
}