Pagini recente » Cod sursa (job #849530) | Cod sursa (job #3040608) | Cod sursa (job #3224812) | Cod sursa (job #3211884) | Cod sursa (job #229667)
Cod sursa(job #229667)
Utilizator |
Paul-Dan Baltescu pauldb |
Data |
11 decembrie 2008 01:43:08 |
Problema |
Deque |
Scor |
Ascuns |
Compilator |
cpp |
Status |
done |
Runda |
|
Marime |
0.55 kb |
#include <stdio.h>
#define maxn 5000010
#define inf 2000000000
int n, k;
int a[maxn];
long long sum;
int main()
{
freopen("deque.in", "r", stdin);
freopen("deque.out", "w", stdout);
int i, j, p, best;
scanf("%d %d ", &n, &k);
for (i = 1; i <= n; i++) scanf("%d ", &a[i]);
best = inf, p = n+1;
for (i=n; i>0; i--)
{
if (a[i] <= best) best = a[i], p = i;
if (p >= i+k)
{
best = inf, p = n+1;
for (j=0; j<k; j++)
if (a[i+j] < best) best = a[i+j], p = i+j;
}
if (i <= n-k+1) sum += best;
}
printf("%lld\n", sum);
return 0;
}