Cod sursa(job #458097)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 23 mai 2010 09:03:40
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <cstdio>

#define file_in "secv2.in"
#define file_out "secv2.out"

int n,k,v[101000],s[101000];

void citire()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n, &k);
	for (int i=1;i<=n;++i)
		 scanf("%d", &v[i]);
}

void solve()
{
	int i;
	int q,suma,sol,inc,sf;
	//sume partiale
	s[0]=0;
	for (i=1;i<=n;++i)
		 s[i]=s[i-1]+v[i];
	
	suma=sol=s[k];
	inc=1;
	sf=k;
	q=1;
	for (i=k+1;i<=n;++i)
	{
		suma+=v[i];
		if (suma<s[i]-s[i-k])
		{
			q=i-k+1;
			suma=s[i]-s[i-k];
		}
		if (sol<suma)
		{
			sol=suma;
			inc=q;
			sf=i;
		}
	}
	suma=0;
	for (i=inc;i<=sf;++i) suma+=v[i];
	printf("%d %d %d", inc,sf,suma);
}

int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}