Cod sursa(job #383960)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 18 ianuarie 2010 20:31:49
Problema Secventa 2 Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<stdio.h>
#define infile "secv2.in"
#define outfile "secv2.out"
#define nmax (50*1001)
#define inf (~(1<<31))
int a[nmax]; //vectorul a
int b[nmax]; //b[i] = valoarea subsecventei maxime ce se termina in i
int c[nmax]; //c[i] = pozitia de inceput a subsecventei ce se termina in i
int n; //lungimea secventei
int k; //lungimea minima a unei subsecvente
int smax=-inf,st,dr; //suma maxima, repsectiv capetele secventei

void read()
{
	int i;
	scanf("%d %d\n",&n,&k);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
}

void init()
{
	int i;
	
	//initial presupunem ca toate subsecventele au un singur element
	for(i=1;i<=n;i++)
		b[i]=a[i],c[i]=i;
	
	//acum facem pentru oricate elemente
	for(i=2;i<=n;i++)
		if(b[i-1] + a[i] > b[i])
			b[i]=b[i-1] + a[i], c[i]=c[i-1];
	
	//transformam vectorul a[i]=a[1]+...+a[i]
	for(i=2;i<=n;i++)
		a[i]+=a[i-1];
}

void solve()
{
	int i;
	
	for(i=k;i<=n;i++)
		if(b[i-k+1] + a[i]-a[i-k+1] > smax)
			smax=b[i-k+1] + a[i]-a[i-k+1],st=c[i-k+1],dr=i;
}

void write()
{
	printf("%d %d %d\n",st,dr,smax);
}

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	
	read();
	init();
	solve();
	write();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}