Cod sursa(job #2888728)
| Utilizator | Data | 11 aprilie 2022 19:41:20 | |
|---|---|---|---|
| Problema | Deque | Scor | 25 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.66 kb |
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
deque <int> minim;
int v[100001];
int main()
{
int n, k;
int rez = 0;
fin >> n >> k;
int i, j;
for (i = 1; i <= n; ++i)
{
fin >> v[i];
while (!minim.empty() && v[minim.back()] >= v[i])
minim.pop_back();
minim.push_back(i);
if (!minim.empty() && minim.front() == i - k)
minim.pop_front();
if (i >= k)
{
int x = v[minim.front()];
rez += x;
}
}
fout << rez;
return 0;
}