Pagini recente » Cod sursa (job #2088755) | Cod sursa (job #2923712) | Cod sursa (job #2342983) | Cod sursa (job #2313589) | Cod sursa (job #2173218)
#include <fstream>
#include <deque>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
deque<pair<int,int> >q;
int main()
{
int n,k,x;
f>>n>>k;
f>>x;
q.push_back(make_pair(x,1));
for(int i=2;i<=k-1;++i){
f>>x;
while(!q.empty() && (q.back().first >= x || q.back().second < (i-k+1)))
q.pop_back();
q.push_back(make_pair(x,i));
}
long long suma = 0;
for(int i=k;i<=n;++i){
f>>x;
while(!q.empty() && (q.back().first >= x || q.back().second < (i-k+1)))
q.pop_back();
q.push_back(make_pair(x,i));
while(!q.empty() && q.front().second < (i-k+1))
q.pop_front();
suma += q.front().first;
}
g<<suma<<'\n';
return 0;
}