Pagini recente » Cod sursa (job #222603) | Cod sursa (job #889018) | Cod sursa (job #974139) | Cod sursa (job #1835231) | Cod sursa (job #35285)
Cod sursa(job #35285)
#include<stdio.h>
#define N 50001
long v[N],q[N],poz[N];
long n,k,p1,p2;
long max,S[N],deque[N];
void citeste()
{long i,j;
freopen("secv2.in","r",stdin);
scanf("%ld %ld\n",&n,&k);
for(i=1;i<=n;i++) scanf("%ld ",&v[i]);
}
void solve()
{long j,i,cap,coada;
for(cap=1,coada=1,i=1;i<=n;i++)
{S[i]=S[i-1]+v[i];
while (cap<=coada && deque[coada]>S[i]) coada--;
deque[++coada]=S[i];
poz[coada]=i;
while (cap<=coada && poz[cap]+k<=i) cap++;
q[i]=poz[cap];
}
max=-100000000;
for(i=k;i<=n;i++)
{j=q[i-k];
if(S[i]-S[j]>max){max=S[i]-S[j]; p1=j+1; p2=i;}
}
}
int main()
{
citeste();
deque[1]=250001;
S[0]=0;
solve();
freopen("secv2.out","w",stdout);
printf("%ld %ld %ld\n",p1,p2,max);
return 0;
}