Pagini recente » Cod sursa (job #483077) | Cod sursa (job #2089150) | Cod sursa (job #2480984) | Cod sursa (job #876350) | Cod sursa (job #1861763)
#include <fstream>
#include <deque>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int n,k;
int i;
struct a{
long long poz;
long long val;
}x;
deque <a>q;
int main()
{
f >> n >> k;
for(i = 1 ; i <= k ; ++i){
f >> x.val;
x.poz = i;
while(!q.empty() && q.back().val > x.val)
q.pop_back();
q.push_back(x);
}
a smin = q.front();
int capats = 1;
int capatd = k;
for(i = k + 1 ; i <= n ; ++i){
f >> x.val;x.poz = i;
capats++;
capatd++;
if(q.front().poz < capats)q.pop_front();
while(!q.empty() && q.back().val > x.val)
q.pop_back();
q.push_back(x);
smin.val += q.front().val;
}
g << smin.val;
return 0;
}