Pagini recente » Cod sursa (job #1384406) | Cod sursa (job #391323) | Cod sursa (job #2171215) | Cod sursa (job #972586) | Cod sursa (job #1464111)
#include <cstdio>
#include <deque>
using namespace std;
const int MAX = 5000010;
const int MAXC = 100010;
//long long a[MAX];
long long N, K;
long long S;
char c[MAXC];
long long p = MAXC - 1;
long long x;
deque< pair<long long, long long> > Q;
void Read();
void Get( long long& x );
void Next();
int main()
{
freopen( "deque.in", "r", stdin );
freopen( "deque.out", "w", stdout );
int i, j;
Read();
for ( i = 1; i <= K - 1; i++ )
{
Get(x);
while ( !Q.empty() && x < Q.back().second )
Q.pop_back();
Q.push_back( make_pair(i, x) );
}
for ( i = K; i <= N; i++ )
{
Get(x);
while ( !Q.empty() && Q.front().first <= i - K )
Q.pop_front();
while ( !Q.empty() && x < Q.back().second )
Q.pop_back();
Q.push_back( make_pair(i, x) );
S += Q.front().second;
}
printf( "%lld\n", S );
fclose(stdin);
fclose(stdout);
return 0;
}
void Read()
{
int i;
Get(N);
Get(K);
/* for ( i = 1; i <= N; i++ )
{
scanf( "%lld", &a[i] );
} */
}
void Get( long long& x )
{
bool sgn = 0;
for ( ; c[p] < '0' || c[p] > '9'; Next() )
if ( c[p] == '-' )
sgn = 1;
for ( x = 0; c[p] >= '0' && c[p] <= '9'; Next() )
x = x * 10 + ( c[p] - '0' );
if ( sgn )
x = -x;
}
void Next()
{
if ( ++p == MAXC )
{
std::fread( c, 1, MAXC, stdin );
p = 0;
}
}