Cod sursa(job #21979)

Utilizator marius135Dumitran Adrian Marius marius135 Data 25 februarie 2007 12:41:50
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>
#define maxn 56000

long s[maxn];
long v[maxn*2];
long poz[maxn*2];
long n,k;


void adauga(long a,long b,long  c,long d,long e)
{
	if(b>=c && b<=d)
		{if(a>v[e]) {v[e]=a;poz[e]=b;}}
	else return;
	if(c==d) return;

	adauga(a,b,c,(c+d)/2,e*2);
	adauga(a,b,(c+d)/2+1,d,e*2+1);
	
}
long mix(long a,long b)
{
	if(v[a]>v[b]) return a;
	return b;
}
long max(long a,long b,long c,long d,long e)
{
	if(c>=a && d<=b) 
		return e;
	if(d<a || b<c) return n*2;
	return mix (max(a,b,c,(c+d)/2,e*2),max(a,b,(c+d)/2+1,d,e*2+1));
	
}


int  main()
{
	freopen("secv2.in","rt",stdin);
	freopen("secv2.out","wt",stdout);
	
	long i,sol=-30000*k,x,w;
	scanf("%ld%ld",&n,&k);
	for(i=1;i<=n*2;i++)
		v[i]=-30000*k;
	for(i=1;i<=n;i++)
		{
		scanf("%ld",&x);
		s[i]=s[i-1]+x;
		adauga(s[i],i,1,n,1);
		}
	long poz1,poz2;
	sol=-1000000000;
	for(i=1;i<=n-k+1;i++)
		{
		w= max(i+k-1,n,1,n,1);
		long ww=w;
		w=v[w]-s[i-1];
		if(w>sol) 
			{sol = w;poz1=i;poz2=poz[ww];}
		}
	printf("%ld %ld %ld",poz1,poz2,sol);
	
}