Pagini recente » Cod sursa (job #321547) | Cod sursa (job #99381) | Cod sursa (job #1592103) | Cod sursa (job #2075643) | Cod sursa (job #2836750)
#define __USE_FILES__
#ifdef __USE_FILES__
#include <fstream>
std::ifstream in("deque.in");
std::ofstream out("deque.out");
#else
#include <iostream>
std::istream& in = std::cin;
std::ostream& out = std::cout;
#endif
// directive preprocesate
#include <algorithm>
#include <array>
#include <cassert>
#include <deque>
#include <functional>
#include <limits>
#include <math.h>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
struct numar {
ll val;
ll index;
numar(ll v = 0, ll i = 0)
{
val = v;
index = i;
}
};
// declaratie functii
void addToQue(std::deque<numar>& qq, numar el)
{
// this is a special add operation
while (!qq.empty() && qq.back().val > el.val) {
qq.pop_back();
}
qq.push_back(el);
}
void printQue(std::deque<numar>& qq)
{
for (auto&& x : qq)
out << x.val << " ";
out << "\n";
return;
}
// declaratii variablile
ll n, k, sum = 0;
std::deque<numar> q;
int main()
{
in >> n >> k;
for (ll i = 1; i <= k; ++i) {
ll v;
in >> v;
addToQue(q, { v, i });
// printQue(q);
}
ll sum = q.front().val;
for (ll i = k + 1; i <= n; ++i) {
ll v;
in >> v;
addToQue(q, { v, i });
while (!q.empty() && i - q.front().index >= k) {
q.pop_front();
}
// printQue(q);
sum += q.front().val; // q.front() este minimul intervalului curent
}
out << sum;
return 0;
}