Pagini recente » Cod sursa (job #3157163) | Cod sursa (job #1133817) | Cod sursa (job #2686058) | Cod sursa (job #415207) | Cod sursa (job #2264715)
#include <iostream>
#include <fstream>
#include <deque>
#include <vector>
using namespace std;
ifstream f1("deque.in");
ofstream f2("deque.out");
vector<long> a;
deque<long> indiciPoz;
long k,n;
long long suma=0;
int main(){
f1>>n>>k;
for(int i=0;i<n;i++){
int x;
f1>>x;
a.push_back(x);
}
indiciPoz.push_front(0);
for(long i=1;i<k;i++){
while(!indiciPoz.empty() && a[i]<a[indiciPoz.back()]){
indiciPoz.pop_back();
}
indiciPoz.push_back(i);
}
suma+=a[indiciPoz.front()];
for(long i=k;i<n;i++){
if(i-k>=indiciPoz.front())
indiciPoz.pop_front();
while(!indiciPoz.empty() && a[i]<a[indiciPoz.back()])
indiciPoz.pop_back();
indiciPoz.push_back(i);
suma+=a[indiciPoz.front()];
}
f2<<suma;
return 0;
}