Cod sursa(job #483650)

Utilizator mottyMatei-Dan Epure motty Data 9 septembrie 2010 16:08:45
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
//secv2
#include<stdio.h>

const int N=50005;

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

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

void Solve()
{
	int bsum=-25001, bcut, lc=1, end;

	for( int i=1; i<k; ++i)
		sp[i]=sp[i-1]+v[i];
		
	for( int i=k; i<=n; ++i)
	{
		if(sp[i-k]<0)
		{
			sp[i-1]-=sp[i-k];
			sp[i-k]=0;
			lc=i-k+1;
		}
		sp[i-k+1]=sp[i-k]+v[i-k+1];
		sp[i]=sp[i-1]+v[i];
		if(sp[i]>bsum)
		{
			bsum=sp[i];
			end=i;
			bcut=lc;
		}
	}
	printf("%d %d %d\n",bcut,end,bsum);
}

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