Cod sursa(job #581544)

Utilizator eukristianCristian L. eukristian Data 14 aprilie 2011 12:21:45
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <cstdio>

int partSum[100002];
int deque[100002];

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

	int n,L,U, back = 1, front = 1;
	int max = -(2<<30);
	deque[1] = 0;
	partSum[0] = 0;

	scanf("%d %d %d", &n, &L, &U);

	for (int i = 1 ; i <= L ; ++i)
	{
		scanf("%d", &partSum[i]);
		partSum[i] += partSum[i - 1];
	}

	for (int i = L + 1 ; i <= n ; ++i)
	{
		scanf("%d", &partSum[i]);
		partSum[i] += partSum[i - 1];

		while (back >= front && partSum[deque[back]] >= partSum[i - L])
			back--;
		deque[++back] = i - L;

		if (deque[front] == i - U - 1)
			front++;

		if (partSum[i] - partSum[deque[front]] > max)
			max = partSum[i] - partSum[deque[front]];
	}

	printf("%d\n", max);
	return 0;
}