Cod sursa(job #281071)

Utilizator roberta_raileanuRoberta Raileanu roberta_raileanu Data 13 martie 2009 19:19:59
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include<stdio.h>
int main()
{
	int i,s[50001]={0},v[50001],j,smax,a,b,sc,pc,n,k;
	freopen("secv2.in","r",stdin);
	freopen("secv2.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&v[i]);
		s[i]=v[i]+s[i-1];
	}
	smax=0;
	/*
	for(i=1;i<=n;i++)
		for(j=1;j<=i;j++)
			s[i]=s[i]+v[j];
	
	for(i=1;i<=n-1;i++)
		//for(j=i;j<=n;j++)
			if(j-i>=k)
				if((s[j]-s[i])>smax)
				{
					smax=s[j]-s[i];
					a=i+1;
					b=j;
				}
	*/
	sc=s[k];
	pc=1;
	smax=sc;
	a=1;
	b=k;
	for(i=k+1 ; i<=n ; ++i)
	{
		if(s[i]-s[i-k] > sc+v[i])
		{
			sc=s[i]-s[i-k];
			pc=i-k+1;
		}
		else
			sc+=v[i];
		if(sc>smax)
		{
			smax=sc;
			a=pc;
			b=i;
		}
	}
	printf("%d %d %d\n",a,b,smax);
	return 0;
}