Pagini recente » Cod sursa (job #1695334) | Cod sursa (job #885500) | Cod sursa (job #2901791) | Cod sursa (job #2174100) | Cod sursa (job #35271)
Cod sursa(job #35271)
#include<stdio.h>
#define N 50001
int v[N],q[N],poz[N];
unsigned int n,k,p1,p2;
long max,S[N],deque[N];
void citeste()
{unsigned int i,j;
freopen("secv2.in","r",stdin);
scanf("%d %d\n",&n,&k);
for(i=1;i<=n;i++) scanf("%d ",&v[i]);
}
void solve()
{unsigned int 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=-1000000;
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]=25001;
solve();
freopen("secv2.out","w",stdout);
printf("%d %d %ld\n",p1,p2,max);
return 0;
}