Cod sursa(job #298046)

Utilizator cristiprgPrigoana Cristian cristiprg Data 5 aprilie 2009 20:07:16
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <cstdio>
#include <climits>

int v[50005];
int main()
{
	FILE *f =fopen("secv2.in", "r");
	int n, k, s = 0, beg = 1, end = 1, ibun = 1, smax = -INT_MAX, sneg = 0;
	fscanf(f, "%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
	{
		fscanf(f, "%d", &v[i]);
		if (i - beg + 1 < k)
			s += v[i], end = i, sneg += v[i];
		else
		{
			//suma pozitiva
			if (s >= 0)
				s += v[i];
			else
				s = v[i], ibun = i;


			//suma negativa
			if (sneg < 0)
				sneg += v[i], sneg -= v[i - k ];




			if (s > smax )
			{
				end = i;
				smax = s;
				beg = ibun;
			}

			if (sneg < 0 && sneg > smax)
			{
				end = i;
				smax = sneg;
				beg = i - k + 1;

			}

		}
	}

	fclose(f);
	f = fopen("secv2.out", "w");
	fprintf(f, "%d %d %d\n", beg, end, smax);
	fclose(f);

	return 0;
}