Cod sursa(job #604956)

Utilizator CristibaluCristi B Cristibalu Data 26 iulie 2011 11:19:58
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <cstdio>
FILE *f,*g;
int a[50100],b[50100],v[50100];
int i,s,s2,mx,mxi,k,n;

int main() {
f=fopen("secv2.in","r");
g=fopen("secv2.out","w");

fscanf(f,"%d%d",&n,&k);

for (i=1;i<=n;i++) 
	fscanf(f,"%d",&v[i]);

a[1]=0;
s=0;
for (i=2;i<=n;i++) {
	if (s+v[i-1]<0) {
		s=0;
		a[i]=s;
		}
	else {
		s=s+v[i-1];
		a[i]=s;
		}
	}

b[n]=0;
s=0;
for (i=n-1;i>=1;i--) {
	if (s+v[i+1]<0) {
		s=0;
		b[i]=s;
		}
	else {
		s=s+v[i+1];
		b[i]=s;
		}
	}

for (s=0,i=1;i<=k;i++)
	s+=v[i];
if (b[i-1]>0) {
	s2=s+b[i-1];
	}
else 
	s2=s;

mx=s2;
mxi=1;

for (i=1;i<=n-k-1;i++) {
	s-=v[i];
	s+=v[i+k];
	s2=s;
	if (a[i+1]>0) s2+=a[i+1];
	if (b[i+k]>0) s2+=b[i+k];
	if (s2>mx) {
		mx=s2;
		mxi=i+1;
		}
	}

int st,dr;
st=mxi;
dr=mxi+k-1;
int con ;

if (a[st]>0) {
	s=0;
	con=a[st];
	while (s!=con) {
		st--;
		s+=v[st];
		}
	}
if (b[dr]>0) {
	s=0;
	con=b[dr];
	while (s!=con) {
		dr++;
		s+=v[dr];
		}
	}

fprintf(g,"%d %d %d",st,dr,mx);

fclose(g);
return 0;

}