Cod sursa(job #229410)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 10 decembrie 2008 02:05:12
Problema Deque Scor Ascuns
Compilator cpp Status done
Runda Marime 0.72 kb
#include <stdio.h>

#define maxn 5000010
#define inf 1000000000
#define maxl 20

int n, k;
int a[maxn];
char buff[maxl];
long long sum;

int main()
{
	freopen("deque.in", "r", stdin);
	freopen("deque.out", "w", stdout);

	int i, j, best, p;

	scanf("%d %d ", &n, &k);

	for (i=1; i<=n; i++) 
	{
		fgets(buff, maxl, stdin);

		for (j = buff[0] == '-'; buff[j]>='0' && buff[j]<='9'; j++) a[i] = a[i] * 10 + buff[j] - '0';
		if (buff[0] == '-') a[i] = -a[i];
	}

	best = inf, p = 0;
	for (i=1; i<=n; i++)
	{
		if (a[i] <= best) best = a[i], p = i;

		if (p == i-k)
		{
			best = inf, p = i;
			for (j=0; j<k; j++) 
				if (a[i-j] < best) best = a[i-j], p = i-j;
		}

		if (i >= k) sum += best;
	}

	printf("%lld\n", sum);

	return 0;
}