Pagini recente » Cod sursa (job #2027814) | Cod sursa (job #1808938) | Cod sursa (job #1879920) | Cod sursa (job #2577703) | Cod sursa (job #1160498)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
struct ceva
{
int val, pos;
};
deque < ceva > deqmin;
int nums[5000001];
ifstream fin("deque.in");
ofstream fout("deque.out");
int n, k;
long long S;
void read()
{
fin >> n;
fin >> k;
for(int i = 1; i <= n; i++)
{
fin >> nums[i];
while(!deqmin.empty() && deqmin.back().val > nums[i])
deqmin.pop_back();
if(!deqmin.empty() && i - deqmin.front().pos + 1 > k)
deqmin.pop_front();
ceva nr;
nr.val = nums[i];
nr.pos = i;
deqmin.push_back(nr);
if(i >= k)
S += deqmin.front().val;
}
}
int main()
{
read();
fout << S;
}