Cod sursa(job #2044439)
| Utilizator | Data | 21 octombrie 2017 10:02:37 | |
|---|---|---|---|
| Problema | Deque | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.6 kb |
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin ("text.in");
ofstream fout ("text.out");
deque <int> q;
int a[5000001];
void elimina (int i) {
while (!q.empty() && a[i] <= a[q.back()]) q.pop_back();
}
int main() {
int n, k;
int i;
int s = 0;
fin >> n >> k;
for (i = 1; i <= n; ++i) fin >> a[i];
for (i = 1; i <= n; ++i) {
elimina(i);
q.push_back(i);
if (q.front() == i - k) q.pop_front();
if (i >= k) s += a[q.front()];
}
fout << s << '\n';
return 0;
}
