Pagini recente » Cod sursa (job #2054326) | Cod sursa (job #1033027) | Cod sursa (job #1104308) | Cod sursa (job #2377147) | Cod sursa (job #2107558)
#include<fstream>
#include<deque>
#define mp make_pair
using namespace std;
ifstream cin("deque.in");
ofstream cout("deque.out");
deque<pair<int, int> >dq;
long long int v, k, n, suma=0;
int main(){
cin >> n >> k;
for (int i = 1; i <= k; i++) {
cin>>v;
pair<int, int>x = mp(v, i);
while (!dq.empty() && dq.back().first > v ){
dq.pop_back();
}
dq.push_back(x);
}
suma+=dq.front().first;
for (int i = k + 1; i <= n; i++){
cin>>v;
while (dq.front().second <= i - k){
dq.pop_front();
}
pair<int, int>x = mp(v, i);
while (!dq.empty() && dq.back().first > v){
dq.pop_back();
}
dq.push_back(x);
suma+=dq.front().first;
}
cout<<suma;
}