Cod sursa(job #89251)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 6 octombrie 2007 13:00:00
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<stdio.h>
int v[50001],sum[50001];
int main(){
	/*
	int i,n,v[50001],j,k,a,b,c;
	long long s,max,y;
	freopen("secv2.in","r",stdin);
	freopen("secv2.out","w",stdout);
	scanf("%d %d",&n,&k);
	for (i=1;i<n+1;++i)
		scanf("%d",&v[i]);
	max=-25001;a=0;b=0;
	for (c=1;c<1+k;++c)
				s+=v[c];
	for (i=1;i<n-k+1;++i){
		y=s;
		for (j=i+k;j<n;++j){
			y+=v[j];
			if (y>max){
			   a=i;
			   b=j;
			   max=y;
			}
		}
		s=s-v[i]+v[i+k];
	}
	*/
	int a,b,aa,sk,s=0,max,i,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]);
		sum[i]=sum[i-1]+v[i];
	}
	max=s=sum[k];
	sk=sum[1]<0?sum[k]-sum[1]:sum[k];
	a=1;
	b=k;
	aa=1;
	for(i=k+1;i<=n;++i){
		if(s<sk){
			s=sk+v[i];
			aa=i-k+1;
		}
		else
			s+=v[i];
		if(s>max){
			max=s;
			a=aa;
			b=i;
		}
		sk+=v[i];
		if(sk<sum[i]-sum[i-k+1])
			sk=sum[i]-sum[i-k+1];
	}
	printf("%d %d %d\n",a,b,max);
	fclose(stdin);
	fclose(stdout);
	return 0;
}