Pagini recente » Cod sursa (job #3262998) | Cod sursa (job #2378685) | Cod sursa (job #419126) | Cod sursa (job #2043420) | Cod sursa (job #931216)
Cod sursa(job #931216)
# include <fstream>
# define maxn 5000010
using namespace std;
int N,K;
int A[maxn],Deque[maxn];
int prim,ultim;
long long S;
int main()
{
ifstream fin("deque.in");
ofstream fout("deque.out");
fin >> N >> K;
prim = 1 , ultim = 0;
for( int i = 1 ; i <= N ; ++i )
{
fin >> A[i];
while ( prim <= ultim && A[i] <= A[ Deque[ultim] ]) ultim--;
Deque[++ultim] = i;
if (Deque[prim] == i-K) prim++;
if (i >= K) S += A[ Deque[prim]];
}
fout << S;
fin.close();
fout.close();
}