Cod sursa(job #197569)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 5 iulie 2008 08:48:06
Problema Secventa 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<stdio.h>
#include<limits.h>
#include<stdlib.h>
#define NMAX 50001

int main(){
freopen("secv2.in","r",stdin);
freopen("secv2.out","w",stdout);
long n,k,i,j,lmax,v[NMAX+1]={0},x,
pi,ps,sl,smax,end,smin=LONG_MAX,pozsmin=1,pozsmax=n,slmax;
const int lsir=7*NMAX;
char sir[lsir],*p;
scanf("%ld%ld\n",&n,&k);
v[0]=0L;
fgets(sir,NMAX*7,stdin);
p=sir;
for(i=1;i<=n;++i){
	x=atoi(p);
	v[i]=v[i-1]+x;
	while(*p!=32&&*p) p++;p++;
	}
if(n==k){smax=v[n];pi=1;ps=n;goto finish;}
lmax=0;smax=LONG_MIN;
for(i=0;i<=n-k+1;++i)
	if(smin>v[i]) {smin=v[i];pozsmin=i;}
slmax=v[n];pozsmax=n;
for(i=n-1;i>=pozsmin+k-1;--i)
	if(slmax<v[i]) {slmax=v[i];pozsmax=i;}
smax=slmax-smin;pi=pozsmin;ps=pozsmax-1;
for(i=pozsmin+k-1;i>=k;--i){
	end=i-k;
	for(j=0;j<=end;++j){
		sl=v[i]-v[j];
		if(sl>smax){smax=sl;pi=j+1;ps=i;}
		}
	}
finish:
printf("%ld %ld %ld",pi,ps,smax);
return 0;
}