Cod sursa(job #1759533)
| Utilizator | Data | 19 septembrie 2016 14:31:52 | |
|---|---|---|---|
| Problema | Deque | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.57 kb |
#include <fstream>
#include <deque>
using namespace std;
int n, k;
//position and value
deque<pair<int, int>> d;
int main() {
ifstream in("deque.in");
ofstream out("deque.out");
in >> n >> k;
long long sol = 0, value;
for (int i = 0; i < n; i++) {
in >> value;
while (!d.empty() && value < d.back().second)
d.pop_back();
d.push_back(make_pair(i, value));
if (i - d.front().first == k)
d.pop_front();
if (i >= k - 1)
sol += d.front().second;
}
out << sol;
return 0;
}