Cod sursa(job #1266176)
| Utilizator | Data | 18 noiembrie 2014 13:54:56 | |
|---|---|---|---|
| Problema | Deque | Scor | 25 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.57 kb |
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream f ("deque.in");
ofstream g ("deque.out");
const int NMAX = 5000000 + 1;
int n, k;
deque <int> D;
int v[NMAX];
void rezolva() {
int x, s = 0;
for (int i = 1; i <= n; i++) {
f >> v[i];
while (!D.empty() && v[i] < v[D.back()]) D.pop_back();
D.push_back(i);
if (i >= k) {
s += v[D.front()];
}
if (i - D.front() + 1 == k) D.pop_front();
}
g << s << '\n';
}
int main() {
f >> n >> k;
rezolva();
return 0;
}
