Pagini recente » Cod sursa (job #517063) | Cod sursa (job #160602) | Cod sursa (job #2224500) | Monitorul de evaluare | Cod sursa (job #3210656)
#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
//#define fin cin
//#define fout cout
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
using ll = long long;
struct cv {
int index;
int value;
};
namespace ano {
template<typename T, typename sumT = long long>
class deque {
private:
// Variables:
list<T> l;
public:
// Deconstructor
~deque() {
this->l.clear();
}
// Basic functions
bool empty() {
return this->l.empty();
}
size_t size() {
return this->l.size();
}
void clear() {
this->l.clear();
}
T& back() {
return this->l.back();
}
T& front() {
return this->l.front();
}
bool activateSum(const bool val) {
this->doSum = val;
this->sum = 0;
}
// Basic control operations
/// Basic input operations
void push_back(const T input) {
this->l.push_back(input);
}
void push_front(const T input) {
this->l.push_front(input);
}
/// Basic output operations
void pop_back() {
this->l.pop_back();
}
void pop_front() {
this->l.pop_front();
}
};
}
ano::deque<cv> dq;
ll n,k;
ll ans;
int main() {
fin >> n >> k;
for (int i = 1; i <= n; i++) {
int rd;
fin >> rd;
while (!dq.empty() && dq.back().value > rd) {
dq.pop_back();
}
dq.push_back({i,rd});
while (!dq.empty() && dq.front().index + k == i) {
dq.pop_front();
}
if (i >= k && n >= i) {
ans += dq.front().value;
}
}
fout << ans;
return 0;
}