Pagini recente » Borderou de evaluare (job #1579594) | Cod sursa (job #26440) | Borderou de evaluare (job #1930421) | Cod sursa (job #2249448) | Cod sursa (job #3349232)
#include <fstream>
#include <deque>
#include <vector>
using namespace std;
long long minSubsequences(const vector<int>& v, const int n, const int k) {
deque <int> d;
long long sum = 0;
for (int i = 0; i < n; i++) {
while (!d.empty() && v[d.back()] >= v[i]) {
d.pop_back();
}
d.push_back(i);
if (d.front() <= i - k) {
d.pop_front();
}
if (i >= k - 1) {
sum += v[d.front()];
}
}
return sum;
}
int main() {
ifstream fin("deque.in");
ofstream fout("deque.out");
int n, k;
fin >> n >> k;
vector <int> v(n);
for (int i = 0; i < n; i++)
fin >> v[i];
fout << minSubsequences(v, n, k);
return 0;
}