Cod sursa(job #2788831)
| Utilizator | Data | 26 octombrie 2021 15:30:38 | |
|---|---|---|---|
| Problema | Deque | Scor | 25 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.68 kb |
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
int main()
{
int n, k, a;
deque<pair<int, int>> min;
int minSum = 0;
fin >> n >> k;
for (int i = 0; i < n; ++i)
{
fin >> a;
while (!min.empty() && min.back().first > a)
{
min.pop_back();
}
min.push_back({a, i});
while (!min.empty() && min.front().second < i - k + 1)
{
min.pop_front();
}
if (i >= k - 1)
{
minSum += min.front().first;
}
}
fout << minSum;
return 0;
}
