Pagini recente » Cod sursa (job #127757) | Cod sursa (job #1164757) | Cod sursa (job #3036732) | Cod sursa (job #98941) | Cod sursa (job #2153684)
#include <fstream>
#include <deque>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
struct numar{
long long int poz;
long long int val;
numar (long long int _a = 0, long long int _b = 0){
poz = _a;
val = _b;
}
};
deque <numar>minime;
int n, k;
int main(){
in >> n >> k;
for (int i = 1; i < k; ++ i){
numar nr;
in >> nr.val;
nr.poz = i;
if (minime.size())
while (minime.back().val >= nr.val && minime.size())
minime.pop_back();
minime.push_back(nr);
}
long long int suma_min = 0;
for (int i = k; i <= n; ++ i){
numar nr;
in >> nr.val;
nr.poz = i;
if (minime.front().poz < i - k + 1)
minime.pop_front();
if (minime.size())
while (minime.back().val >= nr.val && minime.size())
minime.pop_back();
minime.push_back(nr);
suma_min += minime.front().val;
}
out << suma_min;
return 0;
}