Cod sursa(job #350201)

Utilizator ProtomanAndrei Purice Protoman Data 23 septembrie 2009 00:29:30
Problema Secventa 5 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <algorithm>
#include <stdio.h>
#include <math.h>

#define MAX 100024

using namespace std;

float maxGs;
int n, x, y, st, fn;
int deqSt[2], deqFn[2];
int deqPr[2][MAX];
int en[MAX];
float prod[MAX];

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

	scanf("%d %d %d", &n, &x, &y);

	for (int i = 1; i <= n; i++)
	{
		float nr;
		scanf("%f", &nr);
		
		en[i] = en[i - 1] + ((nr < 0)? 1 : 0);
		prod[i] = prod[i - 1] + log(fabs(nr));
	}

	deqSt[0] = deqSt[1] = 1;
	deqFn[1] = deqFn[1] = 0;

	for (int i = x; i <= n; i++)
	{
		int par = en[i - x] % 2;
		deqFn[par]++;
		deqPr[par][deqFn[par]] = i - x;
		for (; deqFn[par] > deqSt[par] && prod[deqPr[par][deqFn[par]]] < prod[deqPr[par][deqFn[par] - 1]]; deqFn[par]--)
			swap(deqPr[par][deqFn[par]], deqPr[par][deqFn[par] - 1]);

		par = en[i] % 2;
		if (deqSt[par] <= deqFn[par])
		{
			float pa = prod[i] - prod[deqPr[par][deqSt[par]]];
			if (pa > maxGs)
			{
				maxGs = pa;
				st = deqPr[par][deqSt[par]] + 1;
				fn = i;
			}
		}

		for (par = 0; par < 2; par++)
			if (deqPr[par][deqSt[par]] <= i - y)
				deqSt[par]++;
	}

	printf("%d %d\n", fn - st + 1, st);

	fclose(stdin);
	fclose(stdout);
	return 0;
}