Pagini recente » Cod sursa (job #2634950) | Cod sursa (job #1493306) | Cod sursa (job #1677413) | Cod sursa (job #2664470) | Cod sursa (job #2205478)
#include <deque>
#include <iostream>
#include <fstream>
using namespace std;
struct elem {
int val, poz;
};
deque<elem> d;
int main() {
ifstream in("deque.in");
ofstream out("deque.out");
long long n, k, val, s=0;
elem aux;
in>>n>>k;
for (int i=1; i<=n; i++) {
in >> val;
aux.val=val;
aux.poz=i;
if(i<=k)
{
while(!d.empty()&&d.back().val>aux.val)
d.pop_back();
d.push_back(aux);
if(i==k)
s=d.front().val;
}
else
{
while(!d.empty()&&d.front().poz<i-k+1)
d.pop_front();
while(!d.empty()&&d.back().val>aux.val)
d.pop_back();
d.push_back(aux);
s+=d.front().val;
}
}
out<<s;
return 0;
}