Cod sursa(job #185046)

Utilizator AndreyPAndrei Poenaru AndreyP Data 24 aprilie 2008 18:26:49
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<stdio.h>
#define N 50005
int v[N],sum[N],n,k;
char c[400000];
int start,stop,st,smax,s;
void citeste()
{
	int i,semn=1,n1=0,aux=0;
	fgets(c,400000,stdin);
	for(i=0; c[i]!='\0'; i++)
	{
		if((c[i]>='0')&&(c[i]<='9'))
			aux=aux*10+(c[i]-'0');
		else
		if(c[i]=='-')
			semn=-1;
		else
		{
			v[++n1]=aux*semn;
			sum[n1]=sum[n1-1]+v[n1];
			semn=1;
			aux=0;
		}
	}
	/*int i;
	for(i=1; i<=n; i++)
	{
		scanf("%d",&v[i]);
		sum[i]=sum[i-1]+v[i];
	}*/
}
void rezolva()
{
	int i;
	smax=s=sum[k];
	start=1;
	stop=k;
	st=1;
	for(i=k+1; i<=n; i++)
	{
		s+=v[i];
		if(s<sum[i]-sum[i-k])
		{
			s=sum[i]-sum[i-k];
			st=i-k+1;
		}
		if(s>smax)
		{
			smax=s;
			stop=i;
			start=st;
		}
	}
	printf("%d %d %d\n",start,stop,smax);
}
int main()
{
	freopen("secv2.in","r",stdin);
	freopen("secv2.out","w",stdout);
	scanf("%d%d\n",&n,&k);
	citeste();
	rezolva();
	return 0;
}