Cod sursa(job #124837)

Utilizator za_wolfpalianos cristian za_wolf Data 19 ianuarie 2008 23:55:10
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<stdio.h>
long iin,ssf,x[50001],i,j,n,m,k,l,nr,s,rez,poz,in,sf;
int main()
{
	freopen("secv2.in","r",stdin);
	freopen("secv2.out","w",stdout);
	scanf("%ld%ld",&n,&k);
	for (i=1;i<=n;i++)
		scanf("%ld",&x[i]);
/*	rez=x[1];
	s=x[1];
	nr=1;
	poz=1;
	while (poz<=n)
	{
		poz++;
		if (x[poz]+s>=0)
		{
			s+=x[poz];
			nr++;
			if (rez<s&&nr>=k) {rez=s;in=poz-nr+1; sf=poz; }
		} else
		{
			if (rez<s&&nr>=k) {rez=s;in=poz-1-nr+1; sf=poz-1; s=0;}
			if (nr>=k) {s=0;nr=0;}
		}
	}
*/
/*	in=1;
	sf=k;
	for (i=1;i<=k;i++)
		s+=x[i];
	rez=s;
	iin=in;
	ssf=sf;
	poz=sf;
	while (poz<=n)
	{
		poz++;
		if (s+x[poz]>=0)
		{
			s+=x[poz];
			sf++;
			if (rez<s&&sf-in+1>=k) {rez=s;iin=in; ssf=sf;}
			if (sf-in+1>k&&x[in]<0)
			{
				s-=x[in];
				in++;
				if (rez<s) {rez=s; iin=in; ssf=sf;}
			}

		}
		else
		{
			in=poz;
			sf=poz+k-1;
			s=0;
			for (i=in;i<=sf;i++)
			s+=x[i];
			poz=sf;
		}
	}

*/
	s=0;
	for (i=1;i<=k;i++)
		s+=x[i];
	rez=s;
	in=1;
	sf=k;
	ssf=k;
	for (j=k+1;j<=n;j++)
	{
		s+=x[sf+1];
		sf++;
		if (s>=rez) {rez=s; ssf=j;}

	}
	s=0;
	for (i=ssf;i>=ssf-k+1;i--)
		s+=x[i];
	rez=s;
	in=ssf-k+1;
	iin=in;
	sf=ssf;
	for (j=ssf-k;j>=1;j--)
	{
		s+=x[in-1];
		in--;
		if (s>rez) {rez=s; iin=in;}
	}
	rez=0;
	for (i=iin;i<=ssf;i++)
		rez+=x[i];

	printf("%ld %ld %ld \n",iin,ssf,rez);
	return 0;
}