Cod sursa(job #359765)

Utilizator DeadEyeNaiba Mihai Lucian DeadEye Data 28 octombrie 2009 11:55:07
Problema Secventa 2 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include<cstdio>
int s[50001];
int main()
{
	int st,sum,smax,n,k,i,j,p1,p2;
	freopen("secv2.in","r",stdin);
	freopen("secv2.out","w",stdout);
	scanf("%d%d",&n,&k);
	s[0]=0;
	p1=1; p2=k; sum=0;
	for(i=1;i<=n;++i)
	{
	    scanf("%d",&s[i]);
		if(i<=k)
			sum+=s[i];
	}
	smax=sum;
	j=k; i=1;
	while(j<=n)
	{
		j++;
		sum=sum+s[j];
		if(j-p1+1>=k && sum>smax)
		{
			smax=sum;
			p2=j;
		}
		st=sum;
		for(i=2;i<=j-k+1;++i)
		{
			sum-=s[i-1];
			if(sum>smax && j-i+1>=k)
			{
				smax=sum;
				p1=i;
				p2=j;
			}
		}
		sum=st;
		if(j-p1>=k && sum-s[p1]>smax)
		{
			smax=sum-s[p1];
			p2=j;
			p1++;
		}
	}
	printf("%d %d %d\n",p1,p2,smax);
	return 0;
}

//Note to self: Cannon highly effective against secv2.