Pagini recente » Cod sursa (job #2462782) | Cod sursa (job #2508322) | Cod sursa (job #2652088) | Cod sursa (job #2249313) | Cod sursa (job #1494127)
#include <fstream>
#include <deque>
using namespace std;
ifstream in( "deque.in" );
ofstream out( "deque.out" );
struct shp
{
long long poz, val;
};
deque <shp> d;
void elimin( int val )
{
while( d.empty()==0 && d.back().val >= val )
{
d.pop_back();
}
}
int main( )
{
long long N, K, x, Ans= 0;
shp aux;
in >> N >> K;
for( long long i= 1; i<=K; ++i )
{
in >> x;
elimin( x );
aux.poz= i;
aux.val= x;
d.push_back( aux );
}
Ans+= d.front().val;
for( long long i= K+1; i<=N; ++i )
{
in >> x;
if( d.front().poz <= i-K ) d.pop_front();
elimin( x );
aux.val= x;
aux.poz= i;
d.push_back( aux );
Ans+= d.front().val;
}
out << Ans << '\n';
return 0;
}