Pagini recente » Cod sursa (job #858100) | Cod sursa (job #1406819) | Cod sursa (job #2898415) | Cod sursa (job #2523375) | Cod sursa (job #3001008)
#include <iostream>
#include <fstream>
#include <deque>
#define ll long long
using namespace std;
ifstream fin("input.in");
ofstream fout("output.out");
//ifstream fin("deque.in");
//ofstream fout("deque.out");
int main()
{
int n, k;
fin >> n >> k;
deque<pair<int, int>> lista; // nr, pozitie
ll suma = 0;
for (int i = 0; i < n; i++)
{
int x;
fin >> x;
// elimina nr din lista >= x
while (!lista.empty() && x <= lista.back().first)
{
lista.pop_back();
}
// adauga nr citit
lista.push_back(make_pair(x, i));
// elimina nr care nu fac parte din secventa
while (!lista.empty() && lista.front().second <= i - k)
{
lista.pop_front();
}
if (i >= k - 1)
{
suma += lista.front().first;
}
}
fout << suma;
}
/*
9 3
-7
9
2
4
-1
5
6
7
1
0 1 2 3 4 5 6 7 8
-7 9 2 4 -1 5 6 7 1
* -7 9 2 -> -7
* 9 2 4 -> 2
* 2 4 -1 -> -1
* 4 -1 5 -> -1
* -1 5 6 -> -1
* 5 6 7 -> 5
* 6 7 1 -> 1
*/