Pagini recente » Cod sursa (job #867017) | Cod sursa (job #3214805) | Cod sursa (job #2125581) | Cod sursa (job #3203773) | Cod sursa (job #935070)
Cod sursa(job #935070)
#include <fstream>
#include <deque>
using namespace std;
class Magic {
int k;
struct my_min
{
int val;
int age;
my_min(int v) {
val = v;
age = 0;
}
};
deque<my_min> mins;
public:
Magic(int k) {
this->k = k;
}
void insert(int x) {
while (!mins.empty() && mins.back().val >= x)
mins.pop_back();
for (int i = 0; i < mins.size(); i++)
mins[i].age++;
mins.push_back(my_min(x));
if (mins.front().age == k)
mins.pop_front();
}
int get_min() {
return mins.front().val;
}
};
void insert(int x) {
}
int main()
{
ifstream in("deque.in");
ofstream out("deque.out");
int n, k, sum = 0, x;
in>>n>>k;
Magic magic(k);
for (int i = 0; i < n; i++) {
in>>x;
magic.insert(x);
if (i >= k-1)
sum += magic.get_min();
}
out<<sum<<endl;
return 0;
}