Pagini recente » Cod sursa (job #203093) | Cod sursa (job #2875411) | Cod sursa (job #334813) | Cod sursa (job #1064159) | Cod sursa (job #283893)
Cod sursa(job #283893)
#include <cstdio>
#include <deque>
#define dim 5000100
using namespace std;
int n, k, sum=0, d[dim];
deque<int> q;
int main()
{
int i;
freopen("deque.in", "r", stdin);
freopen("deque.out", "w", stdout);
scanf("%d %d\n", &n, &k);
for (i=1; i<=n; i++) scanf("%d\n", &d[i]);
for (i=1; i<=k; i++)
{
while (!q.empty() && d[i]<d[q.back()])
q.pop_back();
q.push_back(i);
}
sum+=d[q.front()];
for (i=k+1; i<=n; i++)
{
while (!q.empty() && d[i]<d[q.back()])
q.pop_back();
q.push_back(i);
while (!q.empty() && q.front()<=i-k) q.pop_front();
sum+=d[q.front()];
}
printf("%d\n", sum);
}