Cod sursa(job #2049)

Utilizator crusRus Cristian crus Data 15 decembrie 2006 19:21:30
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <stdio.h>
#define input "secv2.in"
#define output "secv2.out"
#define nmax 50001
long pstart,pfinish,n,smax,i,k;
long v[nmax];    // vectorul initial
long pr[nmax];    // vectorul de pozitii
long suma[nmax]; // suma max de poz i de orice pozitie
long max[nmax];  // suma max de poz i de lungime cel putin k
long s[nmax];    // suma 1-i
long l[nmax];    // poz de inceput a secventei i
void read()
{
	FILE *fin;
	fin=fopen(input,"r");
	fscanf(fin,"%ld %ld",&n,&k);
	for (i=1;i<=n;i++)		
		fscanf(fin,"%ld",&v[i]);			
	fclose(fin);
}
void write()
{
	FILE *fout;
	fout=fopen(output,"w");
	fprintf(fout,"%ld %ld %ld",pstart,pfinish,smax);
	fclose(fout);
}
void solve()
{
	smax=-30000;
	for (i=1;i<k;i++)
		{
		 s[i]=v[i]+s[i-1];
		 if (suma[i-1]<=0)
			 if (v[i]<=0) {suma[i]=0; pr[i]=0;}
			    else {suma[i]=v[i]; pr[i]=1;}
			 else
				 if (suma[i-1]+v[i]>0) {suma[i]=suma[i-1]+v[i]; pr[i]=pr[i-1]+1;}
		}
	for (i=k;i<=n;i++)
		{
		 s[i]=v[i]+s[i-1];
		 if (suma[i-1]<=0)
			 if (v[i]<=0) {suma[i]=0; pr[i]=0;}
			    else {suma[i]=v[i]; pr[i]=1;}
			 else
				 if (suma[i-1]+v[i]>0) {suma[i]=suma[i-1]+v[i]; pr[i]=pr[i-1]+1;}		
		 if (suma[i-k]>0) {max[i]=s[i]-s[i-k]+suma[i-k]; l[i]=k+pr[i-k];}
		    else
			{max[i]=s[i]-s[i-k]; l[i]=k;}
			if (max[i]>smax) {smax=max[i]; pstart=i+1-l[i]; pfinish=i;};
		}
}
int main()
{
	read();
	solve();
	write();
	return 0;
}