Pagini recente » Cod sursa (job #889066) | Cod sursa (job #1506323) | Cod sursa (job #2883369) | Cod sursa (job #2657508) | Cod sursa (job #47181)
Cod sursa(job #47181)
#include <stdio.h>
#define input "secv2.in"
#define output "secv2.out"
#define nmax 50002
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=-2000000000;
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;
}