Cod sursa(job #99328)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 11 noiembrie 2007 10:16:37
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<stdio.h>
int v[50000],suma[50000];
int main(){
	int s,p,n,i,a,b,max=-1000000000,k;
	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]);
		suma[i]=suma[i-1]+v[i];
	}
	/*
	suma[0]=0;
	for (i=1;i<=n-k+1;++i){
		for (j=i+k-1;j<n+1;++j)
			if (suma[j]-suma[i-1]>max){
				max=suma[j]-suma[i-1];
				a=i;
				b=j;
			}
	}
	*/
	p=a=1;
	b=k;
	s=max=suma[k];
	for (i=k+1;i<=n;++i){
		if(suma[i]-suma[i-k]>s+v[i]){
			s=suma[i]-suma[i-k];
			p=i-k+1;
		}
		else
			s+=v[i];
		if(s>max){
			a=p;
			b=i;
			max=s;
		}
	}
	printf("%d %d %d",a,b,max);
	return 0;
}