Cod sursa(job #213010)

Utilizator ilincaSorescu Ilinca ilinca Data 8 octombrie 2008 09:33:48
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <stdio.h>

#define maxn 50005
#define MAX -2000000000


int k, n, sp [maxn], v [maxn];


void scan ()
{
	int i, j;
	scanf ("%d%d", &n, &k);
	for (i=1; i<=n; ++i)
	{
		scanf ("%d", &v [i]);
		sp [i]=sp [i-1] + v [i];
	}
}

void sum ()
{
	int sc=sp[k-1], i, poz, a, b, max=MAX;
	for (i=k; i<=n; ++i)
	{
		//sc=cea mai buna suma formata cu cel putin k elem, avand ultimul termen v[i-1]
		sc+=v[i];//sc=cea mai buna suma... cu cel putin k+1 elem, avand ultimul v[i]
		if(sp[i]-sp[i-k] > sc)
		{
			poz = i-k+1;
			sc = sp[i] - sp[i-k];
		}
		if (max < sc)
		{
			max=sc;
			a=poz;
			b=i;
		}
	}
	printf ("%d %d %d\n", a, b, max);
}

int main ()
{
	freopen ("secv2.in", "r", stdin);
	freopen ("secv2.out", "w", stdout);
	scan ();
	sum ();
	return 0;
}