Pagini recente » Cod sursa (job #2531593) | Cod sursa (job #43496) | Cod sursa (job #2789911) | Cod sursa (job #46086) | Cod sursa (job #603905)
Cod sursa(job #603905)
#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("sev2.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;
}