Pagini recente » Cod sursa (job #1276774) | Cod sursa (job #191784) | Rating Bogdan Surdu (MasterOfLore) | Cod sursa (job #1298265) | Cod sursa (job #1277071)
#include <fstream>
#include<iostream>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
int n, k, st, dr, dq[5000001], v[5000001];
void stanga( int i )
{
if ( i - dq[st] == k )
st++;
}
void dreapta( int i )
{
while( st <= dr && v[i] <= v[dq[dr]] )
dr--;
dq[++dr] = i;
}
int main()
{
int i, s = 0;
in >> n >> k;
for ( i = 1; i <= n; i++ )
in >> v[i];
for ( i = 1; i <= n; i++ )
{
stanga(i);
dreapta(i);
if ( i >= k && i <= n - k + 1 )
s+= v[dq[st]];
}
out << s;
return 0;
}