Cod sursa(job #284233)
Utilizator | Cotofana Cristian cotofana | Data | 21 martie 2009 12:27:24 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.5 kb |
#include <cstdio>
#include <deque>
#define dim 5000100
using namespace std;
int n, k, d[dim];
long long sum=0;
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<=n; i++)
{
while (!q.empty() && d[i]<d[q.back()])
q.pop_back();
q.push_back(i);
if (q.front()==i-k) q.pop_front();
if (i>=k) sum+=d[q.front()];
}
printf("%lld\n", sum);
}