Cod sursa(job #443934)

Utilizator sliceskullcandySlice Skull Candy sliceskullcandy Data 18 aprilie 2010 22:10:32
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
//infoarena
//sliceskullcandy

#include <stdio.h>

long i,j,N,max,x,y,L,R,a[50002],D[50002],K,nr,s;

int main()
{
	freopen("secv2.in","r",stdin);

	scanf("%ld%ld",&N,&K);
	for(i=1;i<=N;i++) scanf("%ld",&a[i]);
	for(i=1;i<=N;i++) D[i]=0;

	x=0;
	y=0;
	i=1;
	nr=K;
	max=-2000000000;
	L=1;
	R=0;
	while(i<=N)
	{
		s=D[i-1]+a[i];
		if(s<0)
		{
			nr=K;
			L=i+1;
			R=i;
			D[i]=0;
		}
		else
		{
			D[i]=D[i-1]+a[i];
			R++;
			nr--;
			if(nr<=0)
				if(max<D[i])
				{
					max=D[i];
					x=L;
					y=R;
				}
		}
		i++;
	}

	if(max==-2000000000)
	{
		s=0;
		for(i=1;i<=K;i++) s+=a[i];
		max=s;
		x=1;
		y=K;
		for(i=K+1;i<=N;i++)
		{
			s-=a[i-K];
			s+=a[i];
			if(max<s)
			{
				max=s;
				x=i-K+1;
				y=i;
			}
		}
	}

	freopen("secv2.out","w",stdout);

	printf("%ld %ld %ld\n",x,y,max);

	return 0;
}